Forbidden graph characterization: Difference between revisions
| Line 67: | Line 67: | ||
|the four-vertex ''diamond graph'' formed by removing an edge from the [[complete graph]] ''K''<sub>4</sub> |
|the four-vertex ''diamond graph'' formed by removing an edge from the [[complete graph]] ''K''<sub>4</sub> |
||
| graph minor |
| graph minor |
||
|<ref>{{citation|last1=El-Mallah|first1=Ehab|last2=Colbourn|first2=Charles L.|title=The complexity of some edge deletion problems|journal=IEEE Transactions on Circuits and Systems|volume=35|issue=3|year=1988|pages=354–362|doi=10.1109/31.1748}}.</ref> |
|||
| |
|||
|- |
|- |
||
Revision as of 01:48, 4 October 2007
A forbidden graph characterization is a method of specifying or describing a family of graphs whereby a graph belongs to the family 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:
The sets of forbidden graphs are aslo called obstruction sets.
The forbidden graph characterization has applications in the computational complexity theory, providing in any cases polynomial-time (although not necessarily most efficient) algorithms for testing whether a graph belongs to a given family.
An early characterization of this kind is the Kuratowski theorem for planar graphs.
The Robertson–Seymour theorem proves the existence of a forbidden minor characterization of a number of graph families.
List of forbidden cahacterizations
 | This list is incomplete; you can help by adding missing items. |
| Family | 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 |
| graphs of fixed genus | a finite obstruction set | graph minor | [1] |
| Subtree graphs | cycles of length 4 or more | induced subgraph | [2] |
| Graph unions of cactus graphs | the four-vertex diamond graph formed by removing an edge from the complete graph K4 | graph minor | [3] |
| ladder graphs | K2,3 and its dual graph | homeomorphic subgraph | [4] |
| General theorems | |||
| a family defined by an induced-hereditary property | a finite obstruction set | induced subgraph | |
| a family defined by an minor-hereditary property | a finite obstruction set | graph minor | Robertson–Seymour theorem |
See also
References
- ^ Reinhard Diestel (2000) "Graph Theory", Springer, ISBN 0387989765 p. 275
- ^ 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
- ^ El-Mallah, Ehab; Colbourn, Charles L. (1988), "The complexity of some edge deletion problems", IEEE Transactions on Circuits and Systems, 35 (3): 354–362, doi:10.1109/31.1748.
- ^ N. Saito, T. Nishizeki (Eds.) (1981) "Graph Theory and Algorithms", Proc. conf., Springer-Verlag, Lecture Notes in Computer Science vol 108, ISBN 3540107045 p. 81