Odd Hadwiger's conjecture for the complements of Kneser graphs

Abstract

A generalization of the four-color theorem, Hadwiger's conjecture is considered as one of the most important and challenging problems in graph theory, and odd Hadwiger's conjecture is a strengthening of Hadwiger's conjecture by way of signed graphs. In this paper, we prove that odd Hadwiger's conjecture is true for the complements $\overline{K}(n,k)$ of the Kneser graphs $K(n,k)$, where $n\ge 2k\ge 4$. This improves a result of G. Xu and S. Zhou (2017) which states that Hadwiger's conjecture is true for this family of graphs. Moreover, we prove that $\overline{K}(n,k)$ contains a 1-shallow complete minor of a special type with order no less than the chromatic number $\chi (\overline{K}(n,k))$, and in the case when $7\le 2k+1\le n\le 3k-1$ the gap between the odd Hadwiger number and chromatic number of $\overline{K}(n,k)$ is $\Omega (1.5^k)$.