Forbidden graph characterization

From Wikipedia, the free encyclopedia

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 also 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.

[edit] List of forbidden characterizations

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, graph minor Definition
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]
Chordal 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 (not necessarily finite) obstruction set induced subgraph
a family defined by an minor-hereditary property a finite obstruction set graph minor Robertson–Seymour theorem

[edit] See also

  • Forbidden subgraph problem

[edit] References

  1. ^ Reinhard Diestel (2000) "Graph Theory", Springer, ISBN 0387989765 p. 275
  2. ^ 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
  3. ^ 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 .
  4. ^ 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

Ļ