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

co.combinatoricsgraph theorygraph-minorshadwiger-conjecture

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:

This seems to me to be an excellent place to look for a counterexample. My own belief is, if it is true for graphs with stability number two then it is probably true in general, so it would be very nice to decide this case.

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.

Related Question