Colouring the square of a planar graph
- \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.
- \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:
In fact, they proved this results for more general classes of graph. This led them to pose the following problem.
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.