TOPICS
Search

Forbidden Minor

A forbidden minor is a graph 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
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
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, 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.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