Question: For which graphs $H$ is the following true?
Every graph that contains $H$ as an induced minor also contains $H$ as an induced topological minor.
Definitions: Let $G$ and $H$ be graphs.
- $H$ is a minor of $G$ if $H$ can be obtained from $G$ by deleting vertices and edges and contracting edges.
- $H$ is an induced minor of $G$ if $H$ can be obtained from $G$ by deleting vertices and contracting edges.
- $H$ is a topological minor of $G$ if $G$ contains a subgraph which is a subdivision of $H$, i.e. it can be obtained from $H$ by subdividing edges.
- $H$ is an induced topological minor of $G$ if $G$ contains an induced subgraph which is a subdivision of $H$.
Background:
It is easy to see that if $G$ contains $H$ as a topological minor, then $G$ contains $H$ as a minor. In the other direction, it is not difficult (see e.g. Proposition 1.7.3 of Reinhard Diestel's book 'Graph Theory', 5th ed) to show that the converse is true if the maximum degree of $H$ is at most 3. In fact, the converse is true for all graphs $G$ if and only if $H$ has maximum degree at most 3.
What about the induced variants of minors and topological minors? Again, it is trivial that every induced topological minor is also an induced minor. For the converse, the graph $H$ certainly needs to be subcubic (max-degree at most 3). But the converse is not true for all subcubic graphs: attach a degree-1 vertex to each vertex of a triangle. This graph contains the claw $K_{1,3}$ as an induced minor - just contract the triangle - but not as an induced topological minor (because it does not contain the claw as an induced subgraph).
Initial thoughts: Extending the above construction, we can derive some necessary conditions on such graphs:
- given a subcubic graph $H$, obtain $G$ from $H$ by replacing every $v \in V(H)$ by a clique $K_v$ of order $d_H(v)$ (the degree of $v$ in $H$) and join, for each edge $uv \in E(H)$, some $x \in K_u$ to some $y \in K_v$, in a way so that every $x \in V(G)$ has exactly one neighbour outside the clique $K_v \ni x$.
- Then $H$ is an induced minor of $G$: just contract each clique $K_v$ to a single vertex.
- $G$ does not contain the claw $K_{1,3}$ as an induced topological minor: for every induced subgraph $G' \subseteq G$, every degree-3 vertex of $G'$ has at least two adjacent neighbors.
- $G$ does not contain $K_4$ as an induced topological minor: suppose $G' \subseteq G$ was an induced subdivision of $K_4$ and let $a_1, a_2, a_3, a_4 \in V(G')$ be the four vertices of degree 3. Let $v \in V(H)$ with $a_1 \in K_v$. Then two of the three neighbours of $a_1$ must again lie in $K_v$ (because $a_1$ has at most one neighbour outside), making them adjacent. Therefore, they must actually be among $a_1, a_2, a_3, a_4$, wlog $a_2, a_3 \in K_v$. But then apply the same argument to $a_4 \in K_w$ for some $w \neq v$ (because $|K_v| = d_H(v) \leq 3$) - a contradiction.
Therefore, if $H$ contains $K_4$ of $K_{1,3}$ as an induced topological minor, then $H$ cannot have the desired property (by transitivity of the 'induced topological minor' relation).
Edit: This construction can be described more succinctly as subdivide every edge once, then take the line graph. As a potential intermediate step to the original question, we may therefore ask
Which graphs are contained as induced topological minors in the line graph of their 1-subdivision?
