Is it possible to calculate Hadwiger's number using $\Delta$ and $ \delta$?

Question

Let $G$ be a simple graph and denote Maximum degree and minimum degree by $\Delta$ and $\delta$ resp. Then

Is it possible to calculate Hadwiger's number using $\Delta$ and $ \delta$?

Answer 1

In one direction, even for $3$-regular graphs, which have $\delta = \Delta = 3$, we can achieve a Hadwiger number which is as large as we like.

Just take a clique $K_n$ and replace each vertex by a cycle on $n-1$ vertices. Put a single edge joining every two different cycles, using a different vertex on each cycle every time. Here's a picture for $n=5$, with different cycles highlighted in different colors:

Contract the vertices of each cycle and you get $K_n$ again, so the Hadwiger number is at least $n$.

In the other direction, we can't put lower bounds on Hadwiger number from $\Delta$ alone - trees can have arbitrarily high $\Delta$ but still have a Hadwiger's number of $2$. However, if $\delta$ is large, then the Hadwiger number must also be large. As this paper shows, every graph with average degree at least $0.64t\log t$ has a $K_t$ minor, so certainly if $\delta$ is at least $0.64t\log t$, then the Hadwiger number is at least $t$.