Cranston–Kim conjecture on list coloring squares of graphs

From papers

Let GG be a connected graph with maximum degree Δ3\Delta\ge 3. Let G2G^2 be its square, and let χ(G2)\chi_{\ell}(G^2) denote the list chromatic number of G2G^2. A Moore graph is a Δ\Delta-regular graph on Δ2+1\Delta^2+1 vertices such that G2=KΔ2+1G^2=K_{\Delta^2+1}.

Cranston–Kim conjecture. If GG is not a Moore graph, then

χ(G2)Δ21.\chi_{\ell}(G^2)\le \Delta^2-1.

The source states that Cranston and Kim proved the conjecture for Δ=3\Delta=3, while Bonamy and Bousquet proved the full claim in the more general setting of online list coloring.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Daniel W. Cranston and Landon Rabern, “Painting Squares in Δ^2-1 Shades”, arXiv:1311.1251 (2014).

Solutions 0

No solutions have been posted yet.