Title: Bipartite graphs are $(\frac{4}{5}-\varepsilon) \fracΔ{\log Δ}$-choosable Show Chinese title

Title: 二分图是$(\frac{4}{5}-\varepsilon) \fracΔ{\log Δ}$-可选择的

Abstract: Alon and Krivelevich conjectured that if $G$ is a bipartite graph of maximum degree $\Delta$, then the choosability (or list chromatic number) of $G$ satisfies $\chi_{\ell}(G) = O \left ( \log \Delta \right )$. Currently, the best known upper bound for $\chi_{\ell}(G)$ is $(1 + o(1)) \frac{\Delta}{\log \Delta}$, which also holds for the much larger class of triangle-free graphs. We prove that for $\varepsilon = 10^{-3}$, every bipartite graph $G$ of sufficiently large maximum degree $\Delta$ satisfies $\chi_{\ell}(G) < (\frac{4}{5} -\varepsilon) \frac{\Delta}{\log \Delta}$. This improved upper bound suggests that list coloring is fundamentally different for bipartite graphs than for triangle-free graphs and hence gives a step toward solving the conjecture of Alon and Krivelevich. Show Chinese abstract

Abstract: Alon 和 Krivelevich 猜测，如果$G$是一个最大度为$\Delta$的二部图，那么$G$的可选择性（或列表色数）满足$\chi_{\ell}(G) = O \left ( \log \Delta \right )$。目前，$\chi_{\ell}(G)$的最佳已知上界是$(1 + o(1)) \frac{\Delta}{\log \Delta}$，这同样适用于更大类的无三角形图。 我们证明对于$\varepsilon = 10^{-3}$，每个最大度数为$\Delta$的足够大的二分图$G$满足$\chi_{\ell}(G) < (\frac{4}{5} -\varepsilon) \frac{\Delta}{\log \Delta}$。 这一改进的上界表明，列表着色对于二分图与无三角形图本质上是不同的，因此为解决 Alon 和 Krivelevich 的猜想提供了一个步骤。