| HAL-Inria | Publications, software ... of Inria's scientists |
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.
Keywords :
line graph
chromatic number
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
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