Choosability of the square of a planar graph with maximum degree four

Daniel W. Cranston, Rok Erman, Riste Škrekovski

Published 2013-03-21, updated 2013-03-22Version 2

We study squares of planar graphs with the aim to determine their list chromatic number. We present new upper bounds for the square of a planar graph with maximum degree $\Delta \leq 4$. In particular $G^2$ is 5-, 6-, 7-, 8-, 12-, 14-choosable if the girth of $G$ is at least 16, 11, 9, 7, 5, 3 respectively. In fact we prove more general results, in terms of maximum average degree, that imply the results above.