Toward Vu's conjecture

Abstract

In 2002, Vu conjectured that graphs of maximum degree $\hat{I}”$ and maximum codegree at most $\hat{I}\P \hat{I}”$ have chromatic number at most $(\hat{I}\P +o(1))\hat{I}”$. Despite its importance, the conjecture has remained widely open. The only direct progress so far has been obtained in the ``dense regime,'' when $\hat{I}\P$ is close to $1$, by Hurley, de Verclos, and Kang. In this paper we provide the first progress in the sparse regime $\hat{I}\P \ll 1$, the case of primary interest to Vu. We show that there exists $\hat{I}{\P }_0>0$ such that for all $\hat{I}\P \in [{\log }^{-32}\hat{I}”,\hat{I}{\P }_0]$, the following holds: if $G$ is a graph with maximum degree $\hat{I}”$ and maximum codegree at most $\hat{I}\P \hat{I}”$, then $\ddot{I}‡(G)\le (\hat{I}{\P }^{1/32}+o(1))\hat{I}”$. 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.

29 pages; comments welcome!