An upper bound for the chromatic number of line graphs

It was conjectured by Reed [B. Reed, ω,αω,α, and χχ, Journal of Graph Theory 27 (1998) 177–212] that for any graph GG, the graph’s chromatic number χ(G)χ(G) is bounded above by ⌈Δ(G)+1+ω(G)2⌉, where Δ(G)Δ(G) and ω(G)ω(G) are the maximum degree and clique number of GG, respectively. In this paper we prove that this bound holds if GG is the line graph of a multigraph. The proof yields a polynomial time algorithm that takes a line graph GG and produces a colouring that achieves our bound.