Strong Perfect Graph Theorem

The theorem, originally conjectured by Berge (1960, 1961), that a graph is perfect iff neither the graph nor its graph complement contains an odd graph cycle of length at least five as an induced subgraph became known as the strong perfect graph conjecture (Golumbic 1980; Skiena 1990, p. 221). The conjecture can be stated more simply as the assertion that a graph is perfect iff it contains no odd graph hole and no odd graph antihole. The proposition can be stated even more succinctly as "a graph is perfect iff it is a Berge graph."

This conjecture was proved in May 2002 following a remarkable sequence of results by Chudnovsky, Robertson, Seymour, and Thomas (Cornuéjols 2002, MacKenzie 2002).

REFERENCES

Berge, C. "Les problèmes de coloration en théorie des graphes." Publ. Inst. Stat. Univ. Paris 9, 123-160, 1960.

Berge, C. "Färbung von Graphen deren sämtliche beziehungsweise deren ungerade Kreise starr sind (Zusammenfassung)." Wissenschaftliche Zeitschrift, Martin Luther Univ. Halle-Wittenberg, Math.-Naturwiss. Reihe, 114-115, 1961.

Berge, C. and Ramírez-Alfonsiin, J. L. "Origins and Genesis." In Perfect Graphs (Ed. J. L. Ramírez-Alfonsín and B. A. Reed). New York: Wiley, pp. 1-12, 2001.

Chvátal, V. "The Strong Perfect Graph Theorem." http://www.cs.concordia.ca/~chvatal/perfect/spgt.html.Cornuéjols, G. "The Strong Perfect Graph Conjecture." International Congress of Mathematics, Beijing, China, 2002, Vol. 3. pp. 547-559. http://integer.gsia.cmu.edu/webpub/SPGCsurvey.pdf.

Fonlupt, J. and Sebő, A. "On the Clique-Rank and the Coloration of Prefect Graphs." In Integer Programming and Combinatorial Optimization, Vol. 1 (Ed. R. Kannan and W. R. Pulleyblank). Waterloo, Ontario: University of Waterloo, pp. 201-216, 1990.

Golumbic, M. C. Algorithmic Graph Theory and Perfect Graphs. New York: Academic Press, 1980.

Jensen, T. R. and Toft, B. Graph Coloring Problems. New York: Wiley, 1995.MacKenzie, D. "Graph Theory Uncovers the Roots of Perfection." Science 297, 38, 2002.

Sebő, A. "On Critical Edges in Minimal Perfect Graphs." J. Combin. Th. B 67, 62-85, 1996.

Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, 1990.

West, D. B. "The Strong Perfect Graph Conjecture." Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, pp. 341-344, 2000.