Disproof of a conjecture by Woodall on the choosability of \(K_{s,t}\)-minor-free graphs
The electronic journal of combinatorics, Tome 29 (2022) no. 3
In 2001, in a survey article about list coloring, 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 $\varepsilon>0$ and $C \ge 1$ there exists $N=N(\varepsilon,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-\varepsilon)(2s+t)$.
@article{10_37236_10994,
author = {Raphael Steiner},
title = {Disproof of a conjecture by {Woodall} on the choosability of {\(K_{s,t}\)-minor-free} graphs},
journal = {The electronic journal of combinatorics},
year = {2022},
volume = {29},
number = {3},
doi = {10.37236/10994},
zbl = {1492.05052},
url = {http://geodesic.mathdoc.fr/articles/10.37236/10994/}
}
Raphael Steiner. Disproof of a conjecture by Woodall on the choosability of \(K_{s,t}\)-minor-free graphs. The electronic journal of combinatorics, Tome 29 (2022) no. 3. doi: 10.37236/10994
Cité par Sources :