Graph-theory open problems

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

AX_kst_minor_free_choosable_2s_t

Source: arXiv:2201.09115 — Disproof of a Conjecture by Woodall

Question 2 · arXiv:2201.09115

arXiv Question high confidence— first stated 2022-01-22
Author: Raphael Steiner

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).

OpenAI manuscript collection partial progress

OpenAI's linear bound $\chi_\ell(G) \le C\,h(G)$ gives $\chi_\ell(G) \le C(s+t-1)$ for $K_{s,t}$-minor-free graphs, linear in $s+t$ even when $s$ and $t$ are comparable. The constant is not optimised, so the bound $2s+t$ remains open.

Why it applies. $K_{s,t}$ is a subgraph of $K_{s+t}$, so a $K_{s,t}$-minor-free graph has no $K_{s+t}$ minor, i.e. $h(G) \le s+t-1$.

Family 157: Graph coloring, clique minors, and Colin de Verdière invariants · Lean formalization scope

These manuscripts were produced by an unreleased OpenAI model and released on 2026-10-06 in github.com/openai/math. They have not been peer reviewed. Lean formalizations are OpenAI's own and cover only the scope stated on their scope page; this project has not run or reviewed them. This is partial progress, so the status above is unchanged.

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

Related conjectures

  • implies List Hadwiger Conjecture ai-proved K_{t-1,t-1} contains a K_t minor: fix a perfect matching a_i b_i and contract the edges a_i b_i for i=1..t-2. The t-2 contracted vertices are pairwise adjacent (a_i is adjacent to b_j for i != j), and the two leftover vertices a_{t-1}, b_{t-1} are adjacent to each other and to every contracted vertex. Hence any K_t-minor-free graph is K_{t-1,t-1}-minor-free, and a positive answer to the source question with s = t' = t-1 gives chi_l(G) <= 2(t-1)+(t-1) = 3t-3 <= 3t for every K_t-minor-free G, which is exactly the List Hadwiger Conjecture with c = 3. Direction is correct: truth of the source forces truth of the target.

View in the relation graph — relations are AI-reviewed, not formally verified.