Toward Vu's conjecture

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 ζ∈ [log⁻³²Δ,ζ₀], 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.