List Colouring Squares of Planar Graphs

Abstract

In 1977, Wegner conjectured that the chromatic number of the square of every planar graph $G$ with maximum degree $\Delta \ge 8$ is at most $\lfloor \frac{3}{2}\Delta \rfloor +1$. We show that it is at most $\frac{3}{2}\Delta (1+o(1))$ (where the $o(1)$ is as $\Delta \to +\infty$), and indeed that this is true for the list chromatic number and for more general classes of graphs.

34 pages

Cited by in corpus (2)

• Entropy compression method applied to graph colorings
• A Unified Approach to Distance-Two Colouring of Graphs on Surfaces