×

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
PDF BibTeX XML Cite
Full Text: Link arXiv