School of Computing
University of Leeds
4pm Tuesday 1st November 2005
Room 2511, JCMB, King's Buildings
A graph G is perfect if for every node induced subgraph H of G, the chromatic number of H equals the size of its largest clique. This class of graphs was introduced by Berge in 1961, when he also conjectured that a graph is perfect if and only if it does not contain an odd hole nor an odd antihole. This famous conjecture was the focus of an enormous amount of exciting research, until it was finally proved by Chudnovsky, Robertson, Seymour and Thomas in 2002, and is now known as the Strong Perfect Graph Theorem. Soon afterwards another key open problem in the area was resolved by Chudnovsky, Cornuejols, Liu, Seymour and Vuskovic, who obtained a polynomial time recognition algorithm for perfect graphs.
One important aspect of perfect graphs is that the following optimization problems: maximum weighted stable set, minimum weighted covering of vertices by cliques, maximum weighted clique and minimum weighted covering of vertices by stable sets, that are NP-complete in general, can be solved in polynomial time for perfect graphs. This result, due to Grotschel, Lovasz and Schrijver, uses the ellipsoid method. The question remains whether these four optimization problems can be solved for perfect graphs by polynomial time purely combinatorial algorithms, avoiding the numerical instability of the ellipsoid method.
This talk will survey the development of the decomposition techniques used in the analysis of perfect graphs that eventually led to the resolution of the Strong Perfect Graph Conjecture and a recognition algorithm for perfect graphs. We also present some of the most recent results in obtaining combinatorial algorithms for finding a clique of maximum weight in some subclasses of perfect graphs.