4
$\begingroup$

It is a well known fact that if $H$ is a graph of maximum degree 3, then $H$ is a minor of a graph $G$ if and only if $H$ is a topological minor of $G$.

Moreover, a graph $G$ has one of $K_{3,3}$ or $K_5$ as minor if and only if it has one of $K_{3,3}$ or $K_5$ as topological minor.

Furthermore, in a writeup by Bruce Reed i saw the following theorem.

Theorem: For any graph $H$, there is a finite set $\mathcal{Z}(H)$ of graphs such that $G$ has $H$ as a minor if and only if $G$ contains a subdivision of some element of $\mathcal{Z}(H)$.

So, my question is under what condition $\mathcal{Z}(H)=\{H\}$ or in other words, what properties must $H$ have so that $\mathcal{Z}(H)=\{H\}$ ?

$\endgroup$
1
  • $\begingroup$ This is the Robertson-Seymour theorem; maybe better understanding of the (very long) proof may help to answer. $\endgroup$ Sep 13, 2017 at 10:42

1 Answer 1

4
$\begingroup$

$\mathcal{Z}(H)$ is the set of graphs obtained from $H$ by splitting vertices of degree $>3$ (the reverse operation to contracting an edge between two vertices, both of degree $\ge 3$, and where the contracted edge is not in any triangle). So (at least when all graphs are assumed to be finite) $\mathcal{Z}(H)=\{H\}$ iff $H$ has maximum degree 3.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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