A Strengthening of Brooks' Theorem for Line Graphs

Abstract

We prove that if $G$ is the line graph of a multigraph, then the chromatic number $\chi(G)$ of $G$ is at most $\max\left\{\omega(G), \frac{7\Delta(G) + 10}{8}\right\}$ where $\omega(G)$ and $\Delta(G)$ are the clique number and the maximum degree of $G$, respectively. Thus Brooks' Theorem holds for line graphs of multigraphs in much stronger form. Using similar methods we then prove that if $G$ is the line graph of a multigraph with $\chi(G) \geq \Delta(G) \geq 9$, then $G$ contains a clique on $\Delta(G)$ vertices. Thus the Borodin-Kostochka Conjecture holds for line graphs of multigraphs.