3
$\begingroup$

Given a graph $G$ with Hadwiger number $h(G)$ and a matching $M$ of $G$. Let $G/M$ be the simple graph obtained by contracting $M$. I am looking for a lower bound on the Hadwiger number of $G/M$ as a function of $h(G)$, say: $$h(G/M) \geq \Omega(\log h(G))$$ (or something like that), or a counter example to show that there is no such bound. Does anybody have any pointer on this?

I think the right bound is: $$h(G/M) = \Omega(h(G))$$ but I am unable to prove (or disprove) it. This is based on two observations: contracting a matching of $K_h$ resulting in $K_{h/2}$ and the similar situation holds for treewidth parameter: contracting a matching of a treewidth $k$ graph resulting in a graph of treewidth at least $k/2$ (though treewidth is loosely connected to Hadwiger number).

From Wikipedia: Hadwiger number $h(G)$ is the largest number $k$ for which the complete graph $K_k$ is a minor of $G$.

$\endgroup$
7
$\begingroup$

There is no such function - here is an example where $h(G)$ is arbitrarily large while $h(G/M) \leq 4$. Make $G$ by taking two copies of an $n \times n$ grid and making every vertex of one grid adjacent to the corresponding vertex of the other grid.

$G$ contains a clique of size $n$ as a minor (i.e $h(G) \geq n$). In particular the $i$'th vertex of the clique is obtained by contracting the $i$'th row of the first grid and the $i$'th column of the second grid and then contracting these two vertices together.

Let $M$ be the matching that connects each vertex of the first grid with its copy in the second grid. $G/M$ is an $n \times n$ grid, so $G/M$ is planar and hence $h(G/M) \leq 4$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.