MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).
show/hide this revision's text 2 deleted 366 characters in body

I don't think even your single graph characterization is quite perfect: the characterization should be that the H-minor-free graphs have a forbidden subgraph characterization iff the graph in H is either a linear forest (a disjoint union of paths) or a disjoint union of a linear forest and a subdivided claw. In each of these two cases, the H-minor-free graphs have a forbidden path or subdivided claw, but it might not be the same as the graph in H.

The case when H has more than one forbidden minor is messiermessy, 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 linear forest + disjoint union of subdivided clawclaws, 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.

show/hide this revision's text 1

I don't think even your single graph characterization is quite perfect: the characterization should be that the H-minor-free graphs have a forbidden subgraph characterization iff the graph in H is either a linear forest (a disjoint union of paths) or a disjoint union of a linear forest and a subdivided claw. In each of these two cases, the H-minor-free graphs have a forbidden path or subdivided claw, but it might not be the same as the graph in H.

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

If H contains a linear forest 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 linear forest + subdivided claw, 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.