Strong perfect graph conjecture

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

• line graph of a bipartite graph
• interval graph (vertices represent line intervals; and edges, their pairwise nonempty intersections)
• chordal graph (every cycle of length at least 4 has a chord, which is an edge not on the cycle but its endvertices are)
• Meyniel graph (every cycle of odd length at least 5 has at least 2 chords)
• strongly perfect graph (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 affirmitive answer to the then perfect graph conjecture.

Perfect graph theorem. (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 coverse was true. This was known to be the strong perfect graph conjecture and was finally answered in the affirmitive 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.

Even though the conjecture has been settled, a lot of subtle structures and deep insights have emerged, and many problems remain open. For example, perfect graph recognition is known to be in co-NP (Lovász 1983). But it is not known whether it is in NP or P.

See also

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