Optimal asymmetric list sizes in bipartite graphs
Problem 3 · arXiv:2004.07457
Status open high confidence
Problem 3 asks for the optimal list-size pairs $(k_A, k_B)$ (with $k_A \leq \Delta_A$, $k_B \leq \Delta_B$) guaranteeing $(k_A,k_B)$-choosability for all bipartite graphs with one-sided maximum degrees $\Delta_A, \Delta_B$. The source paper itself establishes several sufficient conditions (e.g., $(1+\varepsilon)\Delta/\log_4\Delta, 2$- and $((1+\varepsilon)\Delta/\log\Delta, \log\Delta)$-choosability in the symmetric case), but the full characterisation of optimal pairs remains open. A 2024 paper (arXiv:2409.01513) improves the symmetric choosability bound to $(\frac{4}{5}-\varepsilon)\Delta/\log\Delta$ but addresses the symmetric setting only and does not cite or directly engage with Problem 3.
Reviewer notes. No follow-up paper resolving Problem 3 found after searching. The problem is inherently open-ended (asks for a full characterisation of optimal pairs), making partial progress hard to pin down. The paper 2409.01513 improves the symmetric upper bound but does not address the asymmetric question. The Springer paper 'Coloring Bipartite Graphs with Semi-small List Size' (doi:10.1007/s00026-022-00633-z) appeared in search results and could be relevant but could not be verified due to a paywall redirect; it was not included.
Context
The authors introduce $(k_A, k_B)$-choosability as an asymmetric generalisation of ordinary list colouring of bipartite graphs, where vertices in part $A$ receive lists of size $k_A$ and vertices in part $B$ receive lists of size $k_B$. Problem 3 asks for the optimal list-size pairs in terms of the one-sided maximum degrees $\Delta_A$ and $\Delta_B$, and subsumes Conjecture 2 as its symmetric special case.
Notes. PDF source — math notation verified readable.
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