Square-coloring codegree conjecture

About 1 year old · traced to

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.

References

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).

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.