Strong Perfect Graph Theorem

The strong perfect graph theorem gives a forbidden-subgraph characterization of perfect graphs, stating that a graph is perfect precisely when it contains neither an odd hole, an induced cycle of odd length five or more, nor an odd antihole, the complement of such a cycle. Claude Berge conjectured the result in 1961, and Maria Chudnovsky, Neil Robertson, Paul Seymour and Robin Thomas announced a proof in 2002, published in 2006, earning a ten thousand dollar prize offered by Gerard Cornuejols at Carnegie Mellon University and the 2009 Fulkerson Prize; Berge had already observed that odd holes and odd antiholes cannot appear in a perfect graph, since both have a clique number of two but a chromatic number of three. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/