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 <>
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

  • HAL Id : hal-01184357, version 1

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. ⟨hal-01184357⟩

Share

Metrics

Record views

224

Files downloads

864