TOPICS
Search

Forbidden Minor


A forbidden minor for a family of graphs is a graph H such that no member of the family contains H 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 K_5 or utility graph K_(3,3) 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).

familyobstruction
apex graphunknown finite number of minors; at least 157 known
forestC_3
linklessly embeddable graph7 Petersen family graphs forbidden minors
outer-cylindrical graph38 forbidden minors
outerplanar graphK_4 and K_(2,3)
pathwidth <=1C_3 and (3,2)-spoke graph
pathwidth <=2110 forbidden minors
planar graphK_5 and K_(3,3)
projective planar graph35 forbidden minors
graphs on a torusunknown finite number of minors; thousands known
treewidth <=2K_4
treewidth <=3K_5, octahedral graph K_(2,2,2), prism graph P_2 square C_5, Wagner graph M_4
treewidth <=4unknown finite number of minors; at least 75 known

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