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

Daniel W. Cranston, Landon Rabern


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.


List coloring, Online list coloring, Paint number, Square, Moore graph

Full Text: PDF