Vu's codegree conjecture for chromatic number

Let GG be a graph. Write Δ2⁡(G)\operatorname{\Delta_2}(G) for its maximum codegree and Δ⁡(G)\operatorname{\Delta}(G) for its maximum degree. Vu's conjecture. Fix ε1,ε2>0\varepsilon_1,\varepsilon_2>0. If

Δ2⁡(G)≥ε1Δ⁡(G),\operatorname{\Delta_2}(G)\geq \varepsilon_1\operatorname{\Delta}(G),

then

χ(G)≤Δ2⁡(G)+ε2Δ2⁡(G),\chi(G)\leq \operatorname{\Delta_2}(G)+\varepsilon_2\operatorname{\Delta_2}(G),

provided Δ⁡(G)\operatorname{\Delta}(G) is sufficiently large. Vu proposed this in 2002, originally for the stronger list chromatic number. The paper proves a bound within 33 of the maximum codegree for claw-free graphs, but the general conjecture remains open.

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.