标题： 向 Vu 的猜想 显示英文标题

标题： Toward Vu's conjecture

摘要： 2002年，Vu猜想，最大度为$\Delta$且最大共同度至多为$\zeta \Delta$的图的色数至多为$(\zeta+o(1))\Delta$。尽管其重要性，该猜想一直未被解决。到目前为止，唯一的直接进展是在“密集区域”，当$\zeta$接近$1$时，由Hurley、de Verclos和Kang获得。在本文中，我们提供了在稀疏区域$\zeta \ll 1$中的首次进展，这是Vu最感兴趣的案例。 我们证明存在$\zeta_0 > 0$，使得对于所有$\zeta \in [\log^{-32}\Delta,\zeta_0]$，以下成立：如果$G$是一个最大度为$\Delta$且最大共同度至多为$\zeta \Delta$的图，则$\chi(G) \leq (\zeta^{1/32} + o(1))\Delta$。 我们从一个更一般的结果推导出这一结论，该结果仅假设任意$s$个顶点的公共邻域是有限的，而不是顶点对的共同度。 我们的更一般结果也适用于列表着色设置，这具有独立的兴趣。 显示英文摘要

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