TOPICS
Search

Forbidden Minor

A graph is a forbidden minor if its presence as a graph minor of a given graph means it is not a member of some family of graphs.

More generally, there may be a family of minors whose presence characterizes if a given graph has some property. 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 simple graph families which have forbidden minor obstructions.

familyobstruction
apex graphunknown finite number of minors; at least 157 known
forestC_3
linklessly embeddable graph7 Petersen family graphs 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
toroidal graphunknown 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, Outerplanar Graph, Projective Planar Graph, Planar Graph, Robertson-Seymour Theorem, Wagner's Theorem

Explore with Wolfram|Alpha

References

Peirce, M. "Minor-Minimal Graph Functions." https://github.com/mikepierce/MMGraphFunctions.

Cite this as:

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

Subject classifications