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$?

## Best Answer

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:Since that survey (2016), there's been a few results in that direction, but still no proof, see Dense minors of graphs with independence number two (2022) by Sergey Norin and Paul Seymour and papers that cite it.