Forbidden graph characterization
A forbidden graph characterization is a method of specifying or describing a category of graphs whereby a graph belongs to the category in question if and only if for the graph in question certain graphs, called forbidden graphs, are not its "parts" of a specified kind, such as:
An early characterization of this kind is the Kuratowski theorem for planar graphs.
List of forbidden cahacterizations
| Category | Forbidden graphs | Relation | Reference |
|---|---|---|---|
| Planar graphs | K5 and K3,3 | homeomorphic subgraph | Kuratowski theorem |
| Planar graphs | K5 and K3,3 | graph minor | Wagner's theorem |
| Subtree graphs | chordless cycles of length 4 or more | subgraph | [1] |
| graph unions of cactus graphs | the four-vertex diamond graph formed by removing an edge from the complete graph K4 | graph minor | ? |
References
- ^ N. Saito, T. Nishizeki (Eds.) (1981) "Graph Theory and Algorithms", Proc. conf., Springer-Verlag, Lecture Notes in Computer Science vol 108, ISBN 3540107045 p. 177