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

https://hal.inria.fr/hal-01184357
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

File

dmAE0130.pdf
Publisher files allowed on an open archive

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

43

Files downloads

546