Decomposing Berge graphs
by
Robin Thomas
Georgia Institute of Technology

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 discuss recent results of Conforti, Cornuejols and Vuskovic, and Robertson, Seymour and the speaker on decompositions of Berge graphs, and their relevance to the SPGC and testing perfectness.

Date received: April 18, 2001