[hal-01184357] An upper bound for the chromatic number of line graphs

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

from HAL : Dernières publications http://ift.tt/1haXcNU