Vu's sharpened chromatic conjecture

Let GG be a graph, with maximum degree Δ(G)\operatorname{\Delta}(G), maximum codegree Δ2(G)\operatorname{\Delta_2}(G), and chromatic number χ(G)\chi(G). Vu's sharpened conjecture. There is a constant C>0C>0 such that

χ(G)max{CΔ(G)logΔ(G), Δ2(G)+3}.\chi(G)\leq \max\left\{\frac{C\operatorname{\Delta}(G)}{\log\operatorname{\Delta}(G)},\ \operatorname{\Delta_2}(G)+3\right\}.

This strengthens the preceding conjecture in the larger-codegree regime and proposes a bound in the smaller-codegree regime, aligning the former with Vizing's theorem. It is presented as an open sharpening.

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

Additional references

2 papers in this index state this conjecture (2025). The statement above is taken from the most recent of them; the others are arXiv:2508.16818.

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.