7-choosability for K₄,₄- and K₃,₅-minor-free graphs

Question 1 · arXiv:2201.09115

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

Status open high confidence

Both questions remain open as of May 2026. The best known upper bound for K_{4,4}-minor-free graphs is 8-choosability (from Jørgensen's earlier result on 7-degeneracy), while no sharp choosability bound is known for K_{3,5}-minor-free graphs. The source paper (Steiner 2022) disproves Woodall's conjecture for sufficiently large comparable s and t but explicitly leaves K_{4,4} and K_{3,5} as the smallest unsettled parameter pairs. A wide web search returned no subsequent paper resolving either question.

Reviewer notes. No follow-up found in 5 web calls. Jørgensen's result gives 8-choosability (via 7-degeneracy) for K_{4,4}-minor-free graphs; closing the gap to 7 and the analogous K_{3,5} question are both open. The conjecture is recent (2022) so absence of evidence is expected, not suspicious.

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

Question. Is every graph without a $K_{4,4}$-minor $7$-choosable? Is every graph without a $K_{3,5}$-minor $7$-choosable?

Context

After disproving Woodall's Conjecture for large comparable $s$ and $t$, the authors identify $K_{4,4}$ and $K_{3,5}$ as the smallest parameter pairs for which the conjecture is not yet settled by prior results, since Jørgensen's result gives only $8$-choosability for $K_{4,4}$-minor-free graphs and no sharp result is known for $K_{3,5}$.

Notes. PDF source — math notation is clear.

Source paper

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