$|G|/\alpha(G) \leq \eta(G)$ where $\eta(G)$ is the Hadwiger number

Let $$G=(V,E)$$ be a finite, simple, undirected graph. The Hadwiger number $$\eta(G)$$ is the maximum $$n\in\mathbb{N}$$ such that $$K_n$$ is a minor of $$G$$.

Hadwiger's celebrated conjecture states that $$\chi(G) \leq \eta(G)$$ for every finite graph $$G$$.

A crude approximation "from below" for $$\chi(G)$$ is $$|V(G)|/\alpha(G)$$ where $$\alpha(G)$$ is the size of the largest independent set in $$G$$. We get $$|V(G)|/\alpha(G) \leq \chi(G)$$ because every coloring is a partition of $$V(G)$$ into independent sets.

Question. Is $$|V(G)|/\alpha(G) \leq \eta(G)$$ for all finite graphs $$G$$?

• Not sure about the state of the art, but there are some approximation results, see e.g. web.math.princeton.edu/~pds/papers/hadwiger/paper.pdf section 4.
– 1001
Commented May 13 at 21:46
• to my memory the bound of Balogh and Kostochka quoted in this Seymour paper remain the state of the art. Commented May 15 at 3:32
• Please use a high-level tag like "co.combinatorics". I added this tag now. Regarding high-level tags, see meta.mathoverflow.net/q/1075 Commented May 17 at 4:54

This weakening is still an open question, even in the very special case of graphs with $$\alpha(G)=2$$ (complements of triangle-free graphs). In other words, do all graphs with independence number two (or "stability number" two in older literature) have a $$K_{\lceil n/2 \rceil}$$ minor? See Open Question 4.8 in Paul Seymour's survey and the comments around it, in particular: