The citation states that Claude Berge introduced the class of perfect graphs in 1960 together with a possible characterization in terms of forbidden subgraphs. The resolution of Berge's strong perfect graph conjecture quickly became one of the most sought after goals in graph theory. The pursuit of the conjecture brought together four important elements: vertex colorings, stable sets, cliques, and clique covers. Moreover, D. R. Fulkerson established connections between perfect graphs and integer programming through his theory of anti-blocking polyhedra. A graph is called perfect if for every induced subgraph H the clique-covering number of H is equal to the cardinality of its largest stable set. The strong perfect graph conjecture states that a graph is perfect if and only if neither it nor its complement contains as an induced subgraph an odd circuit having at least five edges. The elegance and simplicity of this possible characterization led to a great body of work in the literature, culminating in the proof by Chudnovsky, Robertson, Seymour and Thomas, announced in May 2002, just one month before Berge passed away. The long, difficult, and creative proof by Chudnovsky et al. is one of the great achievements in discrete mathematics.
