# 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.
Keywords :
Document type :
Conference papers
Domain :
Complete list of metadata

Cited literature [14 references]

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

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

Record views