### An upper bound for the chromatic number of line graphs

*Andrew D. King, Bruce A. Reed, Adrian R. Vetta*

#### Abstract

It was conjectured by Reed [reed98conjecture] that for any graph G, the graph's chromatic number χ(G) is bounded above by ⌈Δ(G) +1 + ω(G) / 2⌉, 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.

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page