# zbMATH — the first resource for mathematics

Painting squares in $$\Delta^2-1$$ shades. (English) Zbl 1339.05124
Summary: D. W. Cranston and S.-J. Kim [J. Graph Theory 57, No. 1, 65–87 (2008; Zbl 1172.05023)] conjectured that if $$G$$ is a connected graph with maximum degree $$\Delta$$ and $$G$$ is not a Moore Graph, then $$\chi_{\ell}(G^2)\leq \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.

##### MSC:
 05C15 Coloring of graphs and hypergraphs 05C12 Distance in graphs
Full Text: