TOPICS
Search

Forbidden Topological Minor


A graph is a forbidden topological minor (also known as a forbidden homeomorphic subgraph) if its presence as a homeomorphic subgraph of a given graph (i.e., there is an isomorphism from some graph subdivision of one graph to some subdivision of the other) means it is not a member of some family of graphs. For example, Kuratowski's theorem states that a graph is planar if it does not contain the complete graph K_5 and utility graph K_(3,3) as a topological minor (homeomorphic subgraph).

The following table summarizes some graph families which have forbidden topological minor obstructions.

familyobstructions
planar graphK_5, K_(3,3)
projective planar graph103 graphs
toroidal graph>250000 graphs

See also

Forbidden Induced Subgraph, Forbidden Minor, Kuratowski's Theorem

Explore with Wolfram|Alpha

Cite this as:

Weisstein, Eric W. "Forbidden Topological Minor." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/ForbiddenTopologicalMinor.html

Subject classifications