Andrew D. King ; Bruce A. Reed ; Adrian R. Vetta

An upper bound for the chromatic number of line graphs
dmtcs:3401 
Discrete Mathematics & Theoretical Computer Science,
January 1, 2005,
DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)

https://doi.org/10.46298/dmtcs.3401
An upper bound for the chromatic number of line graphsArticle
Authors: Andrew D. King ^{1}; Bruce A. Reed ^{1}; Adrian R. Vetta ^{1}
0000000190065745##NULL##NULL
Andrew D. King;Bruce A. Reed;Adrian R. Vetta
1 School of Computer Science [Montréal]
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.