6
votes
Accepted
Does the weak Hadwiger conjecture imply the Hadwiger conjecture?
Well, it is possible that both (WH) and (H) are true, in which case (WH) implies (H).
If on the other hand, you are asking if there is a short proof of (H) assuming (WH), then the answer is no. ...
- 32.1k
4
votes
Accepted
$|G|/\alpha(G) \leq \eta(G)$ where $\eta(G)$ is the Hadwiger number
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 (...
- 196
3
votes
Accepted
Complete minors of the grid graphs $\mathbb{Z}^n$
Either I am missing something or for $n>2$ you have $m(n)=\infty$. It is enough to show this for $n=3$. Choose any $m$ and a set of edges in $E_3$ which is the union of the following three sets:
$\...
- 3,041
Only top scored, non community-wiki answers of a minimum length are eligible