A report on the demise of the Alon-Krivelevich conjecture
There is an integer $D_0$ such that, for every integer $D\ge D_0$ and every integer $g\ge3$, there is a simple bipartite $D$-regular graph $H$ of girth at least $g$ whose ordinary and adaptable choice numbers satisfy\[ ch(H)\ge ch_a(H)\ge \left(\frac{1+\sqrt2}{64}+o(1)\right)\frac{(\ln D)^2}{\ln\ln D}.\]The error depends only on $D$. Thus no finite girth condition depending only on the maximum degree forces a universal logarithmic choosability bound. We also transfer non-$k$-choosability from arbitrary bipartite graphs to regular bipartite graphs of any prescribed girth, increasing the maximum degree by a factor depending only on $k$.
Authors
- Ross J. Kang (ORCID: https://orcid.org/0000-0002-4219-593X)
Institutions
- University of Amsterdam (NL)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-12
- DOI
- https://doi.org/10.5281/zenodo.24171100
- Primary Topic
- Advanced Graph Theory Research
- Type
- article
- Field-Weighted Citation Impact
- 0.00