Disproof of a Conjecture by Woodall

2022/01/22 by Raphael Steiner, Steiner, Raphael
Mathematics · #05C15 #05C83 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C15 #msc:05C83

paper · pdf · doi:10.48550/arxiv.2201.09115

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

arxiv created 2022/01/22 · arxiv updated 2022/01/25

Abstract

In 2001, Woodall conjectured that for every pair of integers s,t ≥ 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 ε>0 and C ≥ 1 there exists N=N(ε,C) ∈ ℕ such that for all integers s,t with N ≤ s ≤ t ≤ Cs there exists a graph without a K_s,t-minor and list chromatic number greater than (1-ε)(2s+t).

Citations

• Improved lower bound for the list chromatic number of graphs with no K_t minor

Related

• Connectivity and choosability of graphs with no K_t minor
• Seymour and Woodall's conjecture holds for graphs with independence number two
• A new upper bound on the chromatic number of graphs with no odd K_t minor
• Disproof of the List Hadwiger Conjecture
• Improved lower bound for the list chromatic number of graphs with no K_t minor