Disproof of a Conjecture by Woodall

Abstract

In 2001, Woodall conjectured that for every pair of integers $s,t\ge 1$, all graphs without a $K_{s,t}$-minor are $(s+t-1)$-choosable. In this note we refute this conjecture in a strong form: We prove that for every choice of constants $\epsilon >0$ and $C\ge 1$ there exists $N=N(\epsilon ,C)\in \mathbb{N}$ such that for all integers $s,t$ with $N\le s\le t\le Cs$ there exists a graph without a $K_{s,t}$-minor and list chromatic number greater than $(1-\epsilon )(2s+t)$.

8 pages. arXiv admin note: text overlap with arXiv:2110.09403