Skip to Main content Skip to Navigation
Conference papers

An upper bound for the chromatic number of line graphs

Abstract : 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.
Complete list of metadata

Cited literature [14 references]  Display  Hide  Download
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Friday, August 14, 2015 - 11:37:13 AM
Last modification on : Thursday, June 18, 2020 - 12:32:05 PM
Long-term archiving on: : Sunday, November 15, 2015 - 10:59:33 AM


Publisher files allowed on an open archive




Andrew D. King, Bruce A. Reed, Adrian R. Vetta. An upper bound for the chromatic number of line graphs. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. pp.151-156, ⟨10.46298/dmtcs.3401⟩. ⟨hal-01184357⟩



Record views


Files downloads