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