Asymmetric Krivelevich–Alon choosability for bipartite graphs

Conjecture 7 · arXiv:2004.07457

arXiv Conjecture high confidence— first stated 2021-08-30

Authors: Noga Alon, Stijn Cambie, Ross J. Kang

Status open medium confidence

Conjecture 7 of Alon–Cambie–Kang posits (k_A,k_B)-choosability of bipartite graphs under three asymmetric degree/list-size regimes. Zhu (arXiv:2008.06040, Annals of Combinatorics 2022/2023) studied the problem in the semi-small list-size regime, strengthened bounds for k_A=2, and stated a unified framework conjecture on general bipartite graphs encompassing all three conditions; this constitutes partial progress but the full conjecture remains open. The improvement by Bradshaw–Mohar–Stacho (arXiv:2409.01513, 2024) on the symmetric Alon–Krivelevich bound does not directly address the asymmetric conditions of Conjecture 7.

Cited literature (1)

partial Coloring bipartite graphs with semi-small list size (2020)

Daniel G. Zhu · Annals of Combinatorics · arXiv:2008.06040 · doi:10.1007/s00026-022-00633-z

Studies asymmetric list coloring in the semi-small list size regime; proves improved bounds when one part has list size 2 and states a unified conjecture on general bipartite graphs encompassing all three conditions of Conjecture 7.

Reviewer notes. Conjecture 7 unifies three asymmetric generalisations of the Krivelevich–Alon conjecture. Zhu (2008.06040) provides partial progress in the semi-small regime and a unified reformulation but does not resolve the conjecture. No full proof or counterexample found in the surveyed literature.

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

Conjecture. Let the positive integers $\Delta_A, \Delta_B, k_A, k_B$ satisfy one of the following. (i) Given $\varepsilon > 0$, we have $\Delta_A, \Delta_B \geq \Delta_0$ for some $\Delta_0 = \Delta_0(\varepsilon)$, and $k_A \geq \Delta_A^\varepsilon$ and $k_B \geq \Delta_B^\varepsilon$. (ii) For some absolute constant $C > 1$, $k_A \geq C \log \Delta_B$ and $k_B \geq C \log \Delta_A$. (iii) $\Delta_A = \Delta_B = \Delta$, and, for some absolute constant $C > 0$, $k_B \geq C(\Delta/\log\Delta)^{1/k_A} \log\Delta$ or $k_A \geq C(\Delta/\log\Delta)^{1/k_B} \log\Delta$. Then any bipartite graph $G = (V = A \cup B, E)$ with parts $A$ and $B$ having maximum degrees at most $\Delta_A$ and $\Delta_B$, respectively, is $(k_A, k_B)$-choosable.

Context

Motivated by the asymptotic behaviour of $(k_A, k_B)$-choosability for complete bipartite graphs (Theorem 6 and Theorem 16), the authors conjecture three concrete asymmetric analogues of the Krivelevich–Alon conjecture. Condition (i) is weaker than Conjecture 2; conditions (ii) and (iii) are stronger. The paper shows Conjecture 7 holds for complete bipartite graphs (Theorem 15) and provides partial progress in the general case via Theorem 4 and its corollaries.

Notes. PDF source — math notation verified readable. Three-part conjecture; each part is a separate asymmetric generalisation of Conjecture 2.

Source paper

Asymmetric list sizes in bipartite graphs
Noga Alon, Stijn Cambie, Ross J. Kang · 2021-08-30
https://arxiv.org/abs/2004.07457 PDF source