Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4654850 | European Journal of Combinatorics | 2007 | 6 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
A.D. King, B.A. Reed, A. Vetta,