Seymour and Woodall’s Conjecture Holds for Graphs with Independence Number Two
Rong Chen, Zijian Deng · SIAM Journal on Discrete Mathematics · 2025
Abstract. Woodall [List colourings of graphs, in Surveys in Combinatorics, Cambridge University Press, Cambridge, UK, 2001, pp. 269–301] (and Seymour independently in [ Discrete Math., 310 (2010), pp. 2637–2654]) proposed a conjecture that every graph [Formula: see text] contains every complete bipartite graph on [Formula: see text] vertices as a minor, where [Formula: see text] is the chromatic number of [Formula: see text]. In this paper, we prove that for each positive integer [Formula: see text] with [Formula: see text], each graph [Formula: see text] with independence number two contains a [Formula: see text]-minor, implying that Seymour and Woodall’s conjecture holds for graphs with independence number two, where [Formula: see text] is the graph obtained from [Formula: see text] by making every pair of vertices on the side of the bipartition of size [Formula: see text] adjacent.