### 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.