Suppose $G$ is a finite simple graph and $\eta(G)$ is the maximum $n\in\mathbb{N}$ such that $K_n$ is a minor of $G$. If $\delta(G)$ is the minimal degree of $G$, do we have $\delta(G)\leq\eta(G)$?
$\begingroup$
$\endgroup$
asked May 27, 2016 at 19:01
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
No, icosahedron does not have $K_5$ as a minor being planar graph.
answered May 27, 2016 at 19:25
$\begingroup$
$\endgroup$
2
This is false by classic results of Kostochka and Thomason. Indeed, the claim is false even if you replace 'minimum degree $t$' with '$t$-connected'. That is, if you define $\nu(t)$ to be the smallest Hadwiger number among all $t$-connected graphs, then Corollary 5 of this paper of Kostochka shows that $\nu(t)$ is $O(\frac{t}{\sqrt{\ln t}})$.
On the other hand, just having average degree at least $(\alpha+o(1))t \sqrt{\ln t}$, where $\alpha=0.638\dots$ is an explicit constant is enough to force a $K_t$-minor.
answered May 27, 2016 at 19:46
-
$\begingroup$ Thanks Tony -- just a little question, do your remarks imply that for any positive integer $n$ there is a finite connected graph $G$ such that $\frac{\eta(G)}{\delta(G)}<\frac{1}{n}$ ? $\endgroup$ Commented Jul 25, 2016 at 7:36
-
$\begingroup$ @DominicvanderZypen Yes, by the first paragraph,for every $t$ there is even a $t$-connected graph $G$ with $\frac{\eta(G)}{\delta(G)}=O(\frac{1}{\sqrt{ \ln t}})$. $\endgroup$ Commented Aug 30, 2017 at 12:37
$\begingroup$
$\endgroup$
2
There are infinite many planar graph , δ(G) =5 but η(G) < 5 definitely.
Let G is a counterexample, H = n*G, H is also a counterexample.
A faked smallest planar graph G (suppose 4-uncolorable), δ(G) =5, is a counterexample.
-
$\begingroup$ Can you provide more details? This answer is pretty thin as currently written $\endgroup$ Commented May 27, 2016 at 23:49
-
$\begingroup$ @David-White Let G = (V,E ),E = 3V-6. If d(Vi) = 5 for all Vi, then V = 12 through solving the equation : 2E = 5V , it is icosahedron, a counterexample . Similarly there are infinite different equations with different conditions ( d(Vi) >= 5) , solve them. Or in a more simple way to understand the conclusion: let G = n*counterexample , G is a counterexample. $\endgroup$– lixingCommented May 28, 2016 at 1:01