An upper bound for the chromatic number of line graphs |
| |
Authors: | AD King BA Reed A Vetta |
| |
Institution: | aSchool of Computer Science, McGill University, Canada |
| |
Abstract: | It was conjectured by Reed B. Reed, ω,α, and χ, Journal of Graph Theory 27 (1998) 177–212] that for any graph G, the graph’s chromatic number χ(G) is bounded above by , 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. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|