Square-coloring codegree conjecture

From papers

Let GG be a graph. Its square G2G^2 is obtained by joining distinct vertices that are connected by a two-edge path in GG. Let Δ(G)\operatorname{\Delta}(G) be the maximum degree, Δ2(G)\operatorname{\Delta_2}(G) the maximum codegree, and χ(G2)\chi(G^2) the chromatic number of the square. Square-coloring conjecture. There is a constant C>0C>0 such that

χ(G2)max{CΔ(G)2logΔ(G), 54(Δ2(G)+2)2}.\chi(G^2)\leq \max\left\{\frac{C\operatorname{\Delta}(G)^2}{\log\operatorname{\Delta}(G)},\ \frac{5}{4}\bigl(\operatorname{\Delta_2}(G)+2\bigr)^2\right\}.

This is an analogue of Vu's conjecture for coloring graph squares and is proposed as an open problem.

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

Linda Cook, Ross J. Kang, Eileen Robinson and Gabriëlle Zwaneveld, “Vu's conjecture holds for claw-free graphs”, arXiv:2510.15553 (2025).

Solutions 0

No solutions have been posted yet.