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 or utility graph as a graph minor. The following table summarizes some simple graph families which have forbidden minor obstructions.
family | obstruction |
apex graph | unknown finite number of minors; at least 157 known |
forest | |
linklessly embeddable graph | 7 Petersen family graphs forbidden minors |
outerplanar graph | and |
pathwidth | and -spoke graph |
pathwidth | 110 forbidden minors |
planar graph | and |
projective planar graph | 35 forbidden minors |
toroidal graph | unknown finite number of minors; thousands known |
treewidth | |
treewidth | , octahedral graph , prism graph , Wagner graph |
treewidth | unknown finite number of minors; at least 75 known |