Painting Squares in $\Delta^2-1$ Shades
Daniel W. Cranston, Landon Rabern · The Electronic Journal of Combinatorics · 2016
Cranston and Kim conjectured that if $G$ is a connected graph with maximum degree $\Delta$ and $G$ is not a Moore Graph, then $\chi_{\ell}(G^2)\le \Delta^2-1$; here $\chi_{\ell}$ is the list chromatic number. We prove their conjecture; in fact, we show that this upper bound holds even for online list chromatic number.