Cranston–Kim conjecture on list coloring squares of graphs

About 13 years old · traced to

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)≤Δ2−1.\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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.