Hadwiger's conjecture for the complements of Kneser graphs
classification
🧮 math.CO
keywords
conjecturegraphhadwigerknesercomplementsgraphssubsetsvertices
read the original abstract
Hadwiger's conjecture asserts that every graph with chromatic number $t$ contains a complete minor of order $t$. Given integers $n \ge 2k+1 \ge 5$, the Kneser graph $K(n, k)$ is the graph with vertices the $k$-subsets of an $n$-set such that two vertices are adjacent if and only if the corresponding $k$-subsets are disjoint. We prove that Hadwiger's conjecture is true for the complements of Kneser graphs.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.