Abstract: A graph is called perfect if for every induced subgraph the size of its largest clique equals the minimum number of colors needed to color its vertices. In 1960's Claude Berge made a conjecture that has become one of the most well-known open problems in graph theory: any graph that contains no induced odd cycles of length greater than three or their complements is perfect. This conjecture is known as the Strong Perfect Graph Conjecture.

We call graphs containing no induced odd cycles of length greater than three or their complements Berge graphs. A stronger conjecture was made recently by Conforti, Cornuejols and Vuskovic that any Berge graph either belongs to one of a few well understood basic classes or has a decomposition that can not occur in a minimal counterexample to Berge's Conjecture. In joint work with Neil Robertson, Paul Seymour and Robin Thomas we were able to prove this conjecture and consequently the Strong Perfect Graph Theorem.