When does graph minor containment imply subgraph containment?

Consider a path of length 3. Any graph G which contains this graph as a minor must also contain it as a subgraph. For paths of any length this is easy to prove.

In general this happens for any graph in which each connected component is either a path or a subdivision of the claw grah. (The claw graph is the star graph on 4 vertices, or the complete bipartite graph $K_{1,3}$.)

Does anyone know where I can find a proof of this fact? I know how to prove it, but if it has already appeared in some book/paper, it's easier for me to cite the result instead.

I am also interested in the following more general question, whose answer I do not know: How does one characterize sets of graphs H={H1,H2,...,Hk}, such that containing any of the Hi as a minor is equivalent to containing some graph from a finite set G={G1,G2,...,Gm} as a subgraph. In other words, for which sets H is H-minor containment equivalent to G-subgraph containment for some finite set G. (Note that this is trivial if we allow G to be infinite.)

For example, containing any graph from the set {path of length 3, claw} as a minor is equivalent to containing any graph from that set as a subgraph. As a non-trivial example, containing any from from {path of length 4, cycle of length 3} as a minor is equivalent to containing one of {path of length 4, cycle of length 3, cycle of length 4} as a subgraph.

Edit: For the single graph problem, I think I have stated a complete characterization of such graphs. I only wish to know if this appears in the literature somewhere. For the second problem I do not know a characterization (other than some special cases), and would welcome any information about the problem.

The case when H has more than one forbidden minor is messy, but here's a partial analysis.

If H contains a linear forest (disjoint union of paths) then some path P_k is forbidden and the H-minor-free graphs are obviously describable by a finite set of forbidden subgraphs (P_k and the expansions of H that do not have a P_k subgraph).

If H does not contain a linear forest or disjoint union of subdivided claws, then the H-minor-free graphs include all subdivided claws. In this case the H-minor-free graphs are obviously not describable by a finite set of forbidden subgraphs -- any minimal forbidden minor of H can have its vertices blown up to degree-three trees and then its edges blown up to long paths so that the local neighborhood of any vertex looks the same as a subdivided claw, producing a graph that is not H-minor-free but looks locally like an H-minor-free graph.

If H does contain a cycle, and doesn't contain a linear forest, then the H-minor-free graphs are again obviously not describable by a finite set of forbidden subgraphs -- long cycles are not H-minor-free but look locally like paths, which are H-minor-free.

If H doesn't contain a linear forest or a cycle, but does contain a linear forest + claw in which only one of the claw edges is subdivided, then the H-minor-free graphs are describable by a finite set of forbidden subgraphs (the subdivided claw and the expansions of H that do not contain it -- because H doesn't contain a path or a cycle, each edge in each forbidden minor of H can only be expanded to a length shorter than the subdivided edge of the forbidden claw).

The remaining case is when H contains linear forest + claw subgraphs, but only those in which two or three of the claw edges have been subdivided, or when it contains graphs with more than one claw component.

• Thanks for the partial analysis. I also had a messy analysis like this. Maybe there is no nice characterization.. About the first problem, your statement differs from mine in two respects. 1) Your characterization allows H to be a disjoint union of a linear forest + 1 subdivided claw, whereas my characterization allows a disjoint union of any number of subdivided claws and a linear forest. Why do you allow only 1 subdivided claw? 2) You said that the forbidden subgraph characterization need not have the same graph as in the H-minor-free characterization. Is there an easy example of this? – Robin Kothari Aug 1 '10 at 4:39
• I think I misread your characterization; you already do allow linear forests etc. Somehow I thought you were only considering graphs that are themselves paths or subdivided claws. I'll remove that part of my answer. – David Eppstein Aug 1 '10 at 7:32

Hello !

Well, first I do not think I read about this in any book I read. Which is not really a surprise, as I did not find many books mentionning graph minors. You will find a chapter about minors at the end of Diestel's book (http://www.math.uni-hamburg.de/home/diestel/), and I think we will otherwise have to wait for Bruce Reed's book on Graph Minors.

To focus on your problem, you can for example say that this property does not hold when your graph is not a forest : you can through edge subdivision arbitrarily increase the girth (length of a smallest cycle) of any graph.It means that if you think finding H (with a cycle) as a minor if G is the same as finding it as a subgraph, then you expect to find in H a cycle of length k. You can now subdivide the edges of G k times, to remove any possible cycle of length <= k, which of course changes nothing to minor containment.

Topological Minors :

The same fact that tells you $K_{1,3}$ has this property can be used to prove that for any $k$, $K_{1,k}$ also has this property.

Actually, let $H$ be any graph with two vertices $u,v$ of degree at least 3. Let $d(u,v)$ be their distance in $H$. Now take a graph $G$ having $H$ as a minor, and subdivide all its edges $d(u,v)+1$ times. Well, now you will not find two vertices of $G$ of degree larger than 3 at distance less than $d(u,v)$, so even though $G$ still contains $H$ as a minor, it does not contain it as a subgraph.

So in order to have this property, you must have a most one vertex of degree larger than 3, and I think this is an equivalence.

Usual minors :

In this case, for any graph $H$, there exists a graph $G$ having $H$ as a minor such that $G$ has maximal degree $3$. So there is no need to look at anything different from $K_{1,3}$ or a path to answer your question :-)

I can not help with your set version for the moment, though... :-)

Nathann

• From looking at the nontrivial example in the last sentence of the original post, which I have not checked, it seems that the request for sets of graphs with this property is quite different than the request for a single graph with this property. – JBL Aug 1 '10 at 2:41
• I believe the graphs that I stated are the only graphs with this property. K_{1,4} does not possess this property, because a degree 4 vertex can be obtained after contracting an edge in a graph which previously only contained degree <= 3 vertices. For example, take the H graph (mathworld.wolfram.com/HGraph.html). This contains K_{1,4} as a minor but not a subgraph. – Robin Kothari Aug 1 '10 at 2:55
• Sorryyyyy !!! I noticed while walking in the street I was talking about topological minors... As it seems I can edit my post, I will immediately make this clear ! – Nathann Cohen Aug 1 '10 at 5:47