Perfect Graphs
by Robin Thomas
Georgia Institute of Technology
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.
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 perfection of an associated graph.
I 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.
Back to the
Discrete Mathematics and its Applications home page.