List chromatic number and maximum degree of bipartite graphs

Status partial high confidence

Alon's conjecture that the list chromatic number of any bipartite graph of maximum degree $\Delta$ is at most $c\log\Delta$ remains open. The best known upper bound has been improved from $(1+o(1))\Delta/\log\Delta$ (Johansson's triangle-free bound) to $(4/5-\varepsilon)\Delta/\log\Delta$ for bipartite graphs specifically (Bradshaw, Mohar, Stacho 2024), but this is still $\Theta(\Delta/\log\Delta)$ rather than the conjectured $O(\log\Delta)$. Partial asymmetric progress was also made by Alon, Cambie, and Kang (2021), showing that in a bipartite graph with equal maximum degree $\Delta$ on both sides, one side can be coloured from lists of size $\log\Delta$ provided the other side uses lists of size $(1+o(1))\Delta/\log\Delta$.

Cited literature (4)

• partial Asymmetric list sizes in bipartite graphs (2021)
  Noga Alon, Stijn Cambie, Ross J. Kang · Annals of Combinatorics · arXiv:2004.07457 · doi:10.1007/s00026-021-00552-5

  Proves that in a bipartite graph with $\Delta_A=\Delta_B=\Delta$, one part can be assigned lists of size $\log\Delta$ and the other $(1+o(1))\Delta/\log\Delta$ and a proper list colouring is guaranteed, giving asymmetric partial progress toward the Alon-Krivelevich conjecture.

• partial Bipartite graphs are $(\frac{4}{5}-\varepsilon) \frac{\Delta}{\log \Delta}$-choosable (2024)
  Peter Bradshaw, Bojan Mohar, Ladislav Stacho · arXiv preprint · arXiv:2409.01513

  Proves that every bipartite graph of sufficiently large maximum degree $\Delta$ satisfies $\chi_\ell(G) < (4/5-\varepsilon)\Delta/\log\Delta$ for $\varepsilon=10^{-3}$, improving Johansson's triangle-free bound and showing list colouring is fundamentally easier for bipartite graphs, but still far from the conjectured $O(\log\Delta)$.

• partial Asymmetric list sizes in bipartite graphs (2021)
  Noga Alon, Stijn Cambie, Ross J. Kang · arXiv preprint · arXiv:2004.07457

  Proves Corollary 10: for any $\varepsilon > 0$ and $\Delta$ large enough, every bipartite graph with maximum degree at most $\Delta$ is $((1+\varepsilon)\Delta/\log^4\Delta,\,2)$- and $((1+\varepsilon)\Delta/\log\Delta,\,\log\Delta)$-choosable, constituting the first asymmetric progress toward the conjecture.

• partial Bipartite graphs are $(\frac{4}{5}-\varepsilon) \fracΔ{\log Δ}$-choosable (2024)
  Peter Bradshaw, Bojan Mohar, Ladislav Stacho · arXiv preprint · arXiv:2409.01513

  Proves that every bipartite graph $G$ of sufficiently large maximum degree $\Delta$ satisfies $\operatorname{ch}(G)<(\frac{4}{5}-\varepsilon)\frac{\Delta}{\log\Delta}$ for $\varepsilon=10^{-3}$, giving the first upper bound with leading constant strictly less than $1$ and showing that list coloring behaves fundamentally differently for bipartite graphs than for general triangle-free graphs.

Reviewer notes. The Zhu (2023) paper on 'semi-small list size' for complete bipartite graphs was verified but focuses on asymmetric list sizes in complete bipartite graphs rather than the original conjecture, so it was omitted from since_posted. The conjecture's gap remains very large: the upper bound is $\Theta(\Delta/\log\Delta)$ and the lower bound from random bipartite graphs is $\Omega(\log\Delta)$. The 2024 Bradshaw-Mohar-Stacho paper is an arXiv preprint as of the review date; journal publication status unknown.

Auto-reviewed 2026-05-08 with claude-sonnet-4-6 (worker 03) (web search enabled).