Back to Search Start Over

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

Authors :
Chen, Rong
Deng, Zijian
Publication Year :
2024

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 \leq \chi(G)$, each graph $G$ with independence number two contains a $K^{\ell}_{\ell,\chi(G)-\ell}$-minor, implying that Seymour and Woodall's conjecture holds for graphs with independence number two, where $K^{\ell}_{\ell,\chi(G)-\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.

Subjects

Subjects :
Mathematics - Combinatorics

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.2406.02643
Document Type :
Working Paper