Title: The Strong Perfect Graph Theorem
Speaker: Maria Chudnovsky, Princeton University
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 know 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. The fundamental question of finding a polynomial time recognition algorithm for perfect graphs has been reduced to finding an algorithm that detects whether a graph contains an odd hole or antihole. Recently we were able find such an algorithm, which is, in fact, independent of the proof of the SPGT.