List of Forbidden Characterizations For Graphs and Hypergraphs
- This list is incomplete; you can help by expanding it.
| Family | Forbidden graphs | Relation | Reference | |
|---|---|---|---|---|
| Forests | loops, pairs of parallel edges, and cycles of all lengths | subgraph | Definition | |
| a loop (for multigraphs) or a triangle K3 (for simple graphs) | graph minor | Definition | ||
| Claw-free graphs | star K1,3 | induced subgraph | Definition | |
| Comparability graphs | induced subgraph | |||
| Triangle-free graphs | triangle K3 | induced subgraph | Definition | |
| Planar graphs | K5 and K3,3 | homeomorphic subgraph | Kuratowski's theorem | |
| K5 and K3,3 | graph minor | Wagner's theorem | ||
| Outerplanar graphs | K4 and K2,3 | graph minor | Diestel (2000), p. 107 | |
| Graphs of fixed genus | a finite obstruction set | graph minor | Diestel (2000), p. 275 | |
| Apex graphs | a finite obstruction set | graph minor | ||
| Linklessly embeddable graphs | The Petersen family | graph minor | ||
| Bipartite graphs | odd cycles | subgraph | ||
| Chordal graphs | cycles of length 4 or more | induced subgraph | ||
| Perfect graphs | cycles of odd length 5 or more or their complements | induced subgraph | ||
| Line graph of graphs | nine forbidden subgraphs (listed here) | induced subgraph | ||
| Graph unions of cactus graphs | the four-vertex diamond graph formed by removing an edge from the complete graph K4 | graph minor | ||
| Ladder graphs | K2,3 and its dual graph | homeomorphic subgraph | ||
| Helly circular-arc graphs | induced subgraph | |||
| split graphs | induced subgraph | |||
| series-parallel (treewidth ≤ 2 branchwidth ≤ 2) | K4 | graph minor | Diestel (2000), p. 327 | |
| treewidth ≤ 3 | K5, octahedron, pentagonal prism, Wagner graph | graph minor | ||
| branchwidth ≤ 3 | K5, octahedron, cube, Wagner graph | graph minor | ||
| Complement-reducible graphs (cographs) | 4-vertex path P4 | induced subgraph | ||
| Trivially perfect graphs | 4-vertex path P4 and 4-vertex cycle C4 | induced subgraph | ||
| Threshold graphs | 4-vertex path P4, 4-vertex cycle C4, and complement of C4 | induced subgraph | ||
| Line graph of 3-uniform linear hypergraphs | a finite list of forbidden induced subgraphs with minimum degree at least 19 | induced subgraph | ||
| Line graph of k-uniform linear hypergraphs, k > 3 | a finite list of forbidden induced subgraphs with minimum edge degree at least 2k2 − 3k + 1 | induced subgraph | ||
| General theorems | ||||
| a family defined by an induced-hereditary property | a (not necessarily finite) obstruction set | induced subgraph | ||
| a family defined by an minor-hereditary property | a finite obstruction set | graph minor | Robertson–Seymour theorem |
Read more about this topic: Forbidden Graph Characterization
Famous quotes containing the words list of, list and/or forbidden:
“Religious literature has eminent examples, and if we run over our private list of poets, critics, philanthropists and philosophers, we shall find them infected with this dropsy and elephantiasis, which we ought to have tapped.”
—Ralph Waldo Emerson (1803–1882)
“Weigh what loss your honor may sustain
If with too credent ear you list his songs,
Or lose your heart, or your chaste treasure open
To his unmastered importunity.”
—William Shakespeare (1564–1616)
“Art is never chaste. It ought to be forbidden to ignorant innocents, never allowed into contact with those not sufficiently prepared. Yes, art is dangerous. Where it is chaste, it is not art.”
—Pablo Picasso (1881–1973)