DMTCS Proceedings, 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)

Font Size:  Small  Medium  Large

An upper bound for the chromatic number of line graphs

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


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

Valid XHTML 1.0 Transitional