This post continues my series on favourite theorems of the twenty-first century. For an overview of the categories and earlier selections, see this post.
My choice for 2002 in Combinatorics—and indeed across all of mathematics—is the celebrated strong perfect graph theorem of Chudnovsky, Robertson, Seymour, and Thomas. The theorem was proved in 2002 and published in 2006 (Chudnovsky et al. 2006).
The chromatic number of a graph , denoted , is the smallest number of colours needed to colour the vertices of so that adjacent vertices receive different colours. Such an assignment is called a proper colouring. Determining chromatic numbers for finite simple graphs—that is, graphs with no loops or multiple edges—is a deep and often difficult subject. A basic lower bound for is the size of the largest clique in , since all vertices in a clique must receive distinct colours. In general, however, this bound need not be sharp. For example, if is an odd cycle of length (an odd hole), then while . Likewise, if is the complement of such a cycle (an odd antihole), then but .
A graph is called perfect if every induced subgraph of satisfies A central problem in the area was to find a simple structural characterization of perfect graphs. The examples above show immediately that a perfect graph cannot contain an odd hole or an odd antihole as an induced subgraph. In 1961, Berge conjectured that this obvious necessary condition is also sufficient. This became known as the strong perfect graph conjecture. It attracted enormous attention and resisted proof for more than forty years.
Chudnovsky, Robertson, Seymour, and Thomas finally settled the conjecture in (Chudnovsky et al. 2006).
This is one of those rare classification theorems whose statement is both clean and unexpectedly definitive. Perfect graphs are defined by a condition involving the chromatic number of every induced subgraph, yet Theorem shows that the entire class can be recognized by forbidding just two families of induced subgraphs. The contrast between the complexity of graph colouring in general and the elegance of this criterion is, to me, part of what makes the theorem so beautiful.
The theorem also had major algorithmic consequences. Building on it, Chudnovsky, Cornuéjols, Liu, Seymour, and Vušković (Chudnovsky et al. 2005) developed a polynomial-time algorithm for recognizing perfect graphs. More precisely, they showed that there exists a polynomial and an algorithm that, given a graph on vertices, performs at most operations and determines whether is perfect.
This fits perfectly with an earlier breakthrough of Grötschel, Lovász, and Schrijver (Grötschel et al. 1988), who gave a polynomial-time method for computing the chromatic number of a perfect graph. Taken together, these results mean that, for any graph , we can determine in polynomial time whether is perfect, and, if it is, compute efficiently.