Forbidden Induced Subgraph

A graph is a forbidden (vertex-)induced subgraph if its presence as a vertex-induced subgraph of a given graph means it is not a member of some family of graphs. For example, a claw-free graph is a graph that does not contain the claw graph K_(1,3) as a vertex-induced subgraph.

More generally, there may be a family of vertex-induced subgraphs whose presence characterizes if a given graph has some property. For example, a simple graph is a line graph iff it does not contain one of the 9 Beineke graphs as a vertex-induced subgraph. The following table summarizes some graph families which have forbidden induced subgraph obstructions.

See also

Claw-Free Graph, Forbidden Minor, Forbidden Subgraph

Explore with Wolfram|Alpha

Cite this as:

Weisstein, Eric W. "Forbidden Induced Subgraph." From MathWorld--A Wolfram Web Resource.

Subject classifications