Strong perfect graph theorem

In graph theory, the strong perfect graph theorem is a forbidden graph characterization of the perfect graphs as being exactly the graphs that have neither odd holes (odd-length induced cycles) nor odd antiholes (complements of odd holes). It was conjectured by Claude Berge in 1961. A proof by Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas was announced in 2002 and published by them in 2006.

The proof of the strong perfect graph theorem won for its authors a $10,000 prize offered by Gérard Cornuéjols of Carnegie Mellon University and the 2009 Fulkerson Prize.

A perfect graph is a graph in which, for every induced subgraph, the size of the maximum clique equals the minimum number of colors in a coloring of the graph; perfect graphs include many well-known graph classes including the bipartite graphs, chordal graphs, and comparability graphs. In his 1961 and 1963 works defining for the first time this class of graphs, Claude Berge observed that it is impossible for a perfect graph to contain an odd hole, an induced subgraph in the form of an odd-length cycle graph of length five or more, because odd holes have clique number two and chromatic number three. Similarly, he observed that perfect graphs cannot contain odd antiholes, induced subgraphs complementary to odd holes: an odd antihole with 2k + 1 vertices has clique number k and chromatic number k + 1, again impossible for a perfect graphs. The graphs having neither odd holes nor odd antiholes became known as the Berge graphs.

...
Wikipedia