A forbidden minor for a family of graphs is a graph such that no member of the family contains as a graph minor.

A set of forbidden minors may characterize membership in a graph family. For example, a planar graph is a graph that does not contain the complete graph or utility graph as a graph minor. The following table summarizes some families of simple graphs which have forbidden minor obstructions. The torus row includes planar graphs, so it concerns genus at most 1, while toroidal graphs have genus exactly 1 (Myrvold and Woodcock 2018, p. 10).

See also

Forbidden Induced Subgraph, Forbidden Subgraph, Forbidden Topological Minor, Kuratowski Reduction Theorem, Linklessly Embeddable Graph, Outer-Cylindrical Graph, Outerplanar Graph, Planar Graph, Projective Planar Graph, Robertson-Seymour Theorem, Wagner's Theorem

Explore with Wolfram|Alpha

References

Archdeacon, D.; Bonnington, C. P.; Dean, N.; Hartsfield, N.; and Scott, K. "Obstruction Sets for Outer-Cylindrical Graphs." J. Graph Th. 38, 42-64, 2001. https://doi.org/10.1002/jgt.1023.Myrvold, W. and Woodcock, J. "A Large Set of Torus Obstructions and How They Were Discovered." Elec. J. Combin. 25, P1.16, 2018. https://doi.org/10.37236/3797.Peirce, M. "Minor-Minimal Graph Functions." https://github.com/mikepierce/MMGraphFunctions.

Referenced on Wolfram|Alpha

Forbidden Minor

Cite this as:

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

Subject classifications