![](/files/happy5.png)
Colouring the square of a planar graph
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ \Delta $](/files/tex/e3f8e135c571143e94f1d4f236326b862080b200.png)
- \item at most
![$ 7 $](/files/tex/daebc9d78b81a4cd1f0e6bae70785e92cf2ce1ea.png)
![$ \Delta =3 $](/files/tex/aced9ebeab44df5a1f3efd1bfb967dd0fe0883c4.png)
![$ \Delta+5 $](/files/tex/a7be33e67abdf15a956bdc393747bb7f75bbd905.png)
![$ 4\leq\Delta\leq 7 $](/files/tex/edab53b759e15d01350d22f54590e6ee9a99bca9.png)
![$ \left\lfloor\frac32\,\Delta\right\rfloor+1 $](/files/tex/d5aa6f60013e17601f35a898a36936e347bc9a8b.png)
![$ \Delta\ge8 $](/files/tex/0782472fc66f76ac853e14ef0f2ded9aaac96451.png)
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.
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ \Delta $](/files/tex/e3f8e135c571143e94f1d4f236326b862080b200.png)
- \item at most
![$ 7 $](/files/tex/daebc9d78b81a4cd1f0e6bae70785e92cf2ce1ea.png)
![$ \Delta =3 $](/files/tex/aced9ebeab44df5a1f3efd1bfb967dd0fe0883c4.png)
![$ \Delta+5 $](/files/tex/a7be33e67abdf15a956bdc393747bb7f75bbd905.png)
![$ 4\leq\Delta\leq 7 $](/files/tex/edab53b759e15d01350d22f54590e6ee9a99bca9.png)
![$ \left\lfloor\frac32\,\Delta\right\rfloor+1 $](/files/tex/d5aa6f60013e17601f35a898a36936e347bc9a8b.png)
![$ \Delta\ge8 $](/files/tex/0782472fc66f76ac853e14ef0f2ded9aaac96451.png)
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:
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ \Delta $](/files/tex/e3f8e135c571143e94f1d4f236326b862080b200.png)
![$ (1+o(1))\,\frac32\,\Delta $](/files/tex/3bd5125caa833bfd0d2506b5188b1240a6313a94.png)
In fact, they proved this results for more general classes of graph. This led them to pose the following problem.
![$ {\cal F} $](/files/tex/f3941009edea56b027602b3a3e226da998b78e0a.png)
![$ {\cal F} $](/files/tex/f3941009edea56b027602b3a3e226da998b78e0a.png)
![$ \chi(G^2)\le \bigl(\frac32+o(1)\bigr) \Delta(G) $](/files/tex/503766a07b9ec6b975f9327434f4c781fb8c8216.png)
![$ G\in{\cal F} $](/files/tex/52f838cc84c888b365b2d562cd3bf8252262a7c1.png)
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.