Hadwiger's conjecture for graphs with forbidden holes

Abstract

Given a graph $G$, the Hadwiger number of $G$, denoted by $h(G)$, is the largest integer $k$ such that $G$ contains the complete graph $K_k$ as a minor. A hole in $G$ is an induced cycle of length at least four. Hadwiger's Conjecture from 1943 states that for every graph $G$, $h(G)\ge \chi (G)$, where $\chi (G)$ denotes the chromatic number of $G$. In this paper we establish more evidence for Hadwiger's conjecture by showing that if a graph $G$ with independence number $\alpha (G)\ge 3$ has no hole of length between $4$ and $2\alpha (G)-1$, then $h(G)\ge \chi (G)$. We also prove that if a graph $G$ with independence number $\alpha (G)\ge 2$ has no hole of length between $4$ and $2\alpha (G)$, then $G$ contains an odd clique minor of size $\chi (G)$, that is, such a graph $G$ satisfies the odd Hadwiger's conjecture.

References in corpus (1)

• On triangles in K_r-minor free graphs