Vu's codegree conjecture for chromatic number

From papers

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.

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.