Painting Squares in ${\Delta }^2-1$ Shades

Abstract

Cranston and Kim conjecture that if $G$ is a connected graph with maximum degree $\Delta$ and $G$ is not a Moore Graph, then ${\chi }_l(G^2)\le {\Delta }^2-1$; here ${\chi }_l$ is the list chromatic number. We prove their conjecture; in fact, this upper bound holds even for online list chromatic number.

23 pages, 10 figures. In version 2, we add a conjecture and 2 figures to the introduction. Results are unchanged