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. As it turns out, the notion of perfect graphs generalizes a large number of phenomena, both in graph theory and in combinatorial optimization. Therefore, the problems of charactering perfect (or minimal imperfect) graphs and finding an efficient recognition algorithm have become well known in both communities. In 1960's Claude Berge made a conjecture that any graph with no induced odd cycles of length greater than three or their complements is perfect (thus, odd cycles of length greater than three and their complements are the only minimal imperfect graphs). 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 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.
Later, in joint work with G. Cornuejols, X, Lui, P.Seymour and K. Vuskovic, we found an algorithm that tests in polynomial time whether a graph is Berge, and therefore perfect.
In my talk I will give an overview of both these results.
