5
$\begingroup$

Kuratowski and Wagner theorems characterize planar graphs in terms of forbidden homeomorphic subgraphs and forbidden minors, respectively. It turns out that both forbidden sets are the same: $\{K_5,K_{3,3}\}$.

Are there other examples where a forbidden set defines the same class of graphs in both ways?

1 Answers 1

6

One example that springs to mind: A (simple) graph is a forest iff it has no $K_3$ as a minor, and also iff it has no $K_3$ as a topological minor (homeomorphic subgraph).

More generally, if the forbidden graphs have maximum degree 3, there's no difference between minors and topological minors (see Proposition 1.7.4 in Diestel's textbook).

  • 0
    It is Proposition 1.7.2 in the second edition.2014-08-03