In 2002, Vu conjectured that graphs of maximum degree Δ and maximum codegree at most ζΔ have chromatic number at most (ζ+o (1) ) Δ. Despite its importance, the conjecture has remained widely open. The only direct progress so far has been obtained in the ``dense regime, '' when ζ is close to 1, by Hurley, de Verclos, and Kang. In this paper we provide the first progress in the sparse regime ζ 1, the case of primary interest to Vu. We show that there exists ζ₀ > 0 such that for all ζ ^-32Δ, ζ₀, the following holds: if G is a graph with maximum degree Δ and maximum codegree at most ζΔ, then χ (G) (ζ^1/32 + o (1) ) Δ. We derive this from a more general result that assumes only that the common neighborhood of any s vertices is bounded rather than the codegrees of pairs of vertices. Our more general result also extends to the list coloring setting, which is of independent interest.
Bradshaw et al. (Fri,) studied this question.