2025/08/22 by Bradshaw, Peter, Dhawan, Abhishek, Methuku, Abhishek +1 · 4 citations
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2508.16818
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 > 0 such that for all ζ∈ [log-32Δ,ζ0], 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.