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 |
claw-free graph | claw graph |
line graph | Beineke graphs |
line graph with | Metelsky graphs |
split graph | |
triangle-free graph | triangle graph |
unswitchable graph |