|
3 |
added a tag
|
||
|
2 | Clarified question | ||
|
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. |
||||
|
1 |
|
||
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.
|
||||

