4
$\begingroup$

Recently I cam across a statement which divides graphs into different classes w.r.t. the complexity of problems on them.

planar < bounded genus < H-minor free < general graphs

My question regards the definition of H-minor free graphs. What I don't understand is that apparently H is not fixed.

Is it true that as long as I can be sure that my (large) graph G doesn't contain some! minor, then some problems might be easier to compute on G then on general graphs regardless of what the actual minor is?

Thank you

  • 0
    Typically in a particular context $H$ is fixed, or is at worst a member of a fixed class of graphs. Take a look at [this link](http://en.wikipedia.org/wiki/Minor_%28graph_theory%29#Major_results_and_conjectures), especially the second and third paragraphs, to see some of the useful effects.2012-01-07

1 Answers 1