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:

• subgraphs,
• graph minors,
• homeomorphic subgraphs
• spanning subgraphs
• induced subgraphs

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

Family	Forbidden graphs	Relation	Reference
Forests	Loops, pairs of parallel edges, and cycles of all lengths	subgraph, graph minor	Definition
Claw-free graphs	star K1,3	induced subgraph	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]
Bipartite graphs	odd cycles	subgraph	[2]
Chordal graphs	cycles of length 4 or more	induced subgraph	[3]
Perfect graphs	cycles of odd length 5 or more or their complements	induced subgraph	[4]
Line graphs	nine forbidden subgraphs	induced subgraph	[5]
Graph unions of cactus graphs	the four-vertex diamond graph formed by removing an edge from the complete graph K4	graph minor	[6]
ladder graphs	K2,3 and its dual graph	homeomorphic subgraph	[7]
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. ^ Béla Bollobás (1998) "Modern Graph Theory", pringer, ISBN 0387984887 p. 9
3. ^ 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
4. ^ Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin (2006), "The strong perfect graph theorem" (^{[dead link]} – ^{Scholar search}), Annals of Mathematics 164: 51–229, http://annals.math.princeton.edu/issues/2006/July2006/ChudnovskyRobertsonSeymourThomas.pdf .
5. ^ Beineke, L. W. (1968), "Derived graphs of digraphs", in Sachs, H.; Voss, H.-J.; Walter, H.-J., Beiträge zur Graphentheorie, Leipzig: Teubner, pp. 17–33 .
6. ^ 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 .
7. ^ 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