When does graph minor containment imply subgraph containment? - MathOverflow

When does graph minor containment imply subgraph containment?

2010-07-31T21:45:25Z

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={H₁,H₂,...,H_k}, such that containing any of the H_i as a minor is equivalent to containing some graph from a finite set G={G₁,G₂,...,G_m} 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.

Answer by Nathann Cohen for When does graph minor containment imply subgraph containment?

2010-08-01T01:28:26Z

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

Answer by David Eppstein for When does graph minor containment imply subgraph containment?

2010-08-01T04:05:10Z

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.