pith. sign in

arxiv: 1503.06912 · v2 · pith:2PUCAPLBnew · submitted 2015-03-24 · 🧮 math.CO

Hadwiger's conjecture for the complements of Kneser graphs

classification 🧮 math.CO
keywords conjecturegraphhadwigerknesercomplementsgraphssubsetsvertices
0
0 comments X
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.