An upper bound for the chromatic number of line graphs

Abstract : It was conjectured by Reed [reed98conjecture] that for any graph $G$, the graph's chromatic number $χ (G)$ is bounded above by $\lceil Δ (G) +1 + ω (G) / 2\rceil$ , where $Δ (G)$ and $ω (G)$ are the maximum degree and clique number of $G$, respectively. In this paper we prove that this bound holds if $G$ is the line graph of a multigraph. The proof yields a polynomial time algorithm that takes a line graph $G$ and produces a colouring that achieves our bound.