Colouring the square of a planar graph

 Importance: Medium ✭✭
 Author(s): Wegner
 Subject: Graph Theory » Coloring » » Vertex coloring
 Keywords:
 Posted by: fhavet on: March 13th, 2013
Conjecture   Let be a planar graph of maximum degree . The chromatic number of its square is
\item at most if , \item at most if , \item at most if .

The square of a graph is the graph on the same set of vertices, in which two vertices are adjacent when their distance in is at most 2.

Wegner [W] also gave examples showing that these bounds would be tight. For , they are the following. For , the examples are planar graphs on with maximum degree whose square is a complete graph.

This conjecture has also been generalized to the list chromatic number.

Conjecture   Let be a planar graph of maximum degree . The list chromatic number of its square is
\item at most if , \item at most if , \item at most if .

Cranston and Kim [CK] showed that the square of every connected graph (non necessarily planar) which is subcubic (i.e., with ) is 8-choosable, except for the Petersen graph. However, the 7-choosability of the square of subcubic planar graphs is still open.

Havet et al. [HHMR] proved the conjecture asymptotically:

Theorem   The square of every planar graph of maximum degree has list chromatic number at most .

In fact, they proved this results for more general classes of graph. This led them to pose the following problem.

Problem   Is it true that for every minor-closed family of graphs (with not the set of all graphs), we have for all ?

Bibliography

[HHMR] F. Havet, J. van den Heuvel, C. McDiarmid, and B. Reed. List Colouring Squares of Planar Graphs. Research Report RR-6586, INRIA, July 2008.

[CK] D. W. Cranston and S.-J. Kim. List-coloring the square of a subcubic graph, J. Graph Theory, 57(1):65--87, 2008.

*[W] G. Wegner. Graphs with given diameter and a coloring problem. Technical report, 1977.

* indicates original appearance(s) of problem.