Is there any general relation between Hadwiger number and Treewidth of a graph? Intuitively I think Hadwiger number is greater than or equal to Treewidth, but I couldn't prove it.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
Planar graphs have Hadwiger number at most 4, but can have arbitrarily high tree width (as evidenced by the $n \times n$ grid).
answered Dec 14, 2015 at 18:31
-
$\begingroup$ Is there any general relation between them? $\endgroup$ Commented Dec 14, 2015 at 18:52
-
2$\begingroup$ Hadwiger number is less than or equal to tree width +1, because tree width at most $k$ is a minor closed property and the tree width of $K_n$ Is $n-1$. $\endgroup$ Commented Dec 14, 2015 at 21:25