Seymour and Woodall's conjecture holds for graphs with independence number two

2024/06/04 by Chen, Rong, Deng, Zijian
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2406.02643

Abstract

Woodall (and Seymour independently) in 2001 proposed a conjecture that every graph G contains every complete bipartite graph on χ(G) vertices as a minor, where χ(G) is the chromatic number of G. In this paper, we prove that for each positive integer ℓ with 2ℓ ≤ χ(G), each graph G with independence number two contains a K^ℓ_{ℓ,χ(G)-ℓ}-minor, implying that Seymour and Woodall's conjecture holds for graphs with independence number two, where K^ℓ_{ℓ,χ(G)-ℓ} is the graph obtained from K_{ℓ,χ(G)-ℓ} by making every pair of vertices on the side of the bipartition of size ℓ adjacent.

Related

• Odd complete bipartite minors in graphs with independence number two
• Hadwiger's Conjecture for some graphs with independence number two
• Disproof of a Conjecture by Woodall
• Dense minors and bipartite independence numbers
• A note on Hadwiger's Conjecture for W₅-free graphs with independence number two