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 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.
family | obstruction(s) |
chordal graph | cycle graphs for , 5, ... |
claw-free graph | claw graph |
line graph | Beineke graphs |
line graph with | Metelsky graphs |
split graph | , , |
triangle-free graph | triangle graph |
unswitchable graph | , , |