List chromatic number bound for K_{s,t}-minor-free graphs

Question 2 · arXiv:2201.09115

arXiv Question high confidence— first stated 2022-01-22

Status open medium confidence

Steiner's paper disproves Woodall's original conjecture (s+t-1 choosability) and proves that the list chromatic number of K_{s,t}-minor-free graphs can exceed (1-ε)(2s+t) for large comparable s and t. Question 2 asks whether the matching upper bound 2s+t always holds; no follow-up paper proving or disproving this universal bound was found in the indexed literature as of 2026.

Reviewer notes. Semantic Scholar citation scraping returned no content (dynamic page); three independent searches found no paper resolving the 2s+t upper bound conjecture. The related arXiv:2110.09403 (Steiner, 2021) concerns K_t-minor-free graphs (single parameter), not K_{s,t}. The 2024 paper arXiv:2406.02643 concerns a different Woodall conjecture (complete bipartite minors vs chromatic number). No follow-up on Question 2 found.

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

Question. Is it true that for all integers $1 \leq s \leq t$, every graph $G$ with $G \not\succeq K_{s,t}$ satisfies $\chi_{\ell}(G) \leq 2s + t$?

Context

Theorem 1 shows that the bound $s+t-1$ in Woodall's conjecture is false for large comparable $s$ and $t$, and that the list chromatic number can exceed $(1-\varepsilon)(2s+t)$; the authors ask whether the matching upper bound $2s+t$ holds universally as the correct asymptotic threshold.

Notes. PDF source — minor-containment symbol interpreted as $\succeq$.

Source paper

Disproof of a Conjecture by Woodall
Raphael Steiner · 2022-01-22
https://arxiv.org/abs/2201.09115 PDF source