Bipartite graphs are $(\frac{4}{5}-\epsilon )\frac{\Delta }{\log \Delta }$-choosable

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 $\epsilon =10^{-3}$, every bipartite graph $G$ of sufficiently large maximum degree $\Delta$ satisfies ${\chi }_{\ell }(G)<(\frac{4}{5}-\epsilon )\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.

8 pages