The theorem, originally conjectured by Berge (1960, 1961), that a graph is perfectiff 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 perfectiff it contains no odd graph hole
and no odd graph antihole. The proposition can
be stated even more succinctly as "a graph is perfectiff 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).
Berge, C. "Les problèmes de coloration en théorie des graphes." Publ. Inst. Stat. Univ. Paris9, 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." Science297, 38, 2002.Sebő,
A. "On Critical Edges in Minimal Perfect Graphs." J. Combin. Th. B67,
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.
