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 ORCID1; Bruce A. Reed 1; Adrian R. Vetta 1

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


Volume: DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
Section: Proceedings
Published on: January 1, 2005
Imported on: May 10, 2017
Keywords: line graph,chromatic number,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]
Funding:
    Source : OpenAIRE Graph
  • Funder: Natural Sciences and Engineering Research Council of Canada

1 Document citing this article

Consultation statistics

This page has been seen 244 times.
This article's PDF has been downloaded 375 times.