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

Abstract

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

Cited by in corpus (1)

• Biclique immersions in graphs with independence number 2