List colouring squares of planar graphs

Frédéric Havet 1 Jan van den Heuvel 2 Colin Mcdiarmid 3 Bruce Reed
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : In 1977, Wegner conjectured that the chromatic number of the square of every planar graph~$G$ with maximum degree $\Delta\ge8$ is at most $\bigl\lfloor\frac32\,\Delta\bigr\rfloor+1$. We show that it is at most $\frac32\,\Delta\,(1+o(1))$, and indeed this is true for the list chromatic number and for more general classes of graphs.
Document type :
Reports
Complete list of metadatas

Cited literature [33 references]  Display  Hide  Download

https://hal.inria.fr/inria-00303303
Contributor : Frederic Havet <>
Submitted on : Monday, July 21, 2008 - 9:57:58 PM
Last modification on : Thursday, February 7, 2019 - 3:08:39 PM
Long-term archiving on : Thursday, October 4, 2012 - 2:48:29 PM

File

RR-6586.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00303303, version 1

Citation

Frédéric Havet, Jan van den Heuvel, Colin Mcdiarmid, Bruce Reed. List colouring squares of planar graphs. [Research Report] RR-6586, INRIA. 2008. ⟨inria-00303303⟩

Share

Metrics

Record views

377

Files downloads

229