Perfect graph
|
|
In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the clique number of that subgraph.
Some of the more well-known perfect graphs are
- the line graph of a bipartite graph
- interval graphs (vertices represent line intervals; and edges, their pairwise nonempty intersections)
- chordal graphs (every cycle of length at least 4 has a chord, which is an edge not on the cycle but its endvertices are)
- Meyniel graphs (every cycle of odd length at least 5 has at least 2 chords)
- strongly perfect graphs (every induced subgraph has an independent set intersecting all its maximal cliques)
Characterization of perfect graphs has known to be difficult. The first breakthrough was the affirmative answer to the then perfect graph conjecture.
Perfect Graph Theorem. (Lovász 1972)
- A graph is perfect if and only if its complement is perfect.
An induced subgraph that is a cycle of odd length at least 5 is called an odd hole. An induced subgraph that is the complement of an odd hole is called an odd antihole. A graph that does not contain any odd holes or odd antihole is called a Berge graph. By virtue of the perfect graph theorem, a perfect graph is necessarily a Berge graph. But it puzzled people for a long time whether the converse was true. This was known to be the strong perfect graph conjecture and was finally answered in the affirmative in May, 2002.
Strong Perfect Graph Theorem. (Chudnovsky, Robertson, Seymour, Thomas 2002)
- A graph is perfect if and only if it is a Berge graph.
As with many results discovered through structural methods, the theorem's proof is long and technical. Efforts towards solving the problem have led to deep insights in the field of structural graph theory, where many related problems remain open. For example, it was proved some time ago that the problem of recognizing Berge graphs is in co-NP (Lovász 1983), but it was not known whether or not it is in P until after the proof of the Strong Perfect Graph Theorem appeared. (A polynomial time algorithm was discovered by Chudnovsky, Cornuéjols, Liu, Seymour, and Vušković shortly afterwards, independent of the Strong Perfect Graph Theorem.)
See also
[1] (http://www.cs.rutgers.edu/~chvatal/perfect/spgt.html) The Strong Perfect Graph Theorem by Vašek Chvàtal, a major contributor to the subject
References
- Berge, Claude (1961). Färbung von Graphen, deren sämtliche bzw. deren ungerade Kreise starr sind. Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 10, 114.
- Chudnovsky, Maria; Cornuéjols, Gérard; Liu, Xinming; Seymour, Paul; Vušković, Kristina (2005). Recognizing Berge graphs. Combinatorica 25, 143–186.
- Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin (announced May 2002, revised March 26, 2004). The strong perfect graph theorem.
- Lovász, László (1972). Normal hypergraphs and the perfect graph conjecture. Discrete Math. 2, 253–267.
- Lovász, László (1972). A characterization of perfect graphs. J. Combin. Theory (B) 13, 95–98.
- Lovász, László (1983). Perfect graphs. In Beineke, Lowell W.; Wilson, Robin J. (Eds), Selected Topics in Graph Theory, Vol. 2, 55–87. Academic Press. ISBN 0-12-086202-6.pl:graf doskonały