Speaker: Robin Thomas
Title: The Strong Perfect Graph Theorem
Abstract:
A graph is perfect if for every induced subgraph, the chromatic number
is equal to the maximum size of a complete subgraph. The Strong Perfect
Graph Conjecture (SPGC) of Berge from 1960 asserts that a graph is
perfect if and only if it has no induced subgraph isomorphic to an odd
cycle of length at least five, or the complement of such a cycle.
(Graphs satisfying the latter condition are called Berge graphs.)
A related open problem is whether perfectness can be tested in polynomial
time.
The class of perfect graphs is important for several reasons. For instance,
many problems of interest in practice that are intractable in general can
be solved efficiently when restricted to the class of perfect graphs. Also,
the question of when a certain class of linear programs always have an integer
solution can be answered in terms of the perfectness of an associated graph.
We will explain why perfect graphs are interesting, and then will discuss
a proof of the SPGC, obtained in joint work with M. Chudnovsky, N. Robertson
and P. Seymour.