The Strong Perfect Graph Theorem

Perfect graphs and Berge graphs

The chromatic number of a graph F is defined as the smallest number of colors that can be assigned to vertices of F in such a way that every two adjacent vertices receive two distinct colors; the clique number of F is defined as the largest number of pairwise adjacent vetices in F.

Trivially, the chromatic number of every graph is at least its clique number. A graph G is called perfect if, for each of its induced subgraphs F, the chromatic number of F equals the largest number of pairwise adjacent vetices in F.

A hole is a chordless cycle of length at least four; an antihole is the complement of such a cycle; holes and antiholes are odd or even according to the parity of their number of vertices. No odd hole is perfect (the clique number of an odd hole is 2 and its chromatic number is 3) and no odd antihole is perfect (the clique number of an antihole with 2k+1 vertices is k and its chromatic number is k+1).

In 1960, Claude Berge

a photograph of Claude Berge

announced the conjecture that a graph is perfect if (and only if) it contains no odd hole and no odd antihole. This conjecture became known as the Strong Perfect Graph Conjecture. Its early history has been described by Berge and Ramírez-Alfonsín.

Chvátal and Sbihi proposed calling a graph a Berge graph if it contains no odd hole and no odd antihole. In this terminology, the Strong Perfect Graph Conjecture asserts that a graph is perfect if (and only if) it is a Berge graph.

Basic objects and structural faults

There are theorems that elucidate the structure of objects in some class C by showing that every object in C has either a prescribed and relatively transparent structure or one of prescribed structural faults, along which it can be decomposed. An early example is the Kronecker Decomposition Theorem: it elucidates the structure of finite Abelian groups by showing that every such group is cyclic (and of a prime power order) or else it is isomorphic to a direct product of other groups. A celebrated example in combinatorics is Seymour's decomposition theorem for regular matroids. Following Burlet and Uhry's work on parity graphs, many people tried to apply this paradigm to Berge graphs. For instance, Michele Conforti, Gérard Cornuéjols, and Kristina Vušković proved in February 2001 that
every square-free Berge graph -- meaning Berge graph containing no hole of length four --either belongs to one of two basic classes (bipartite graphs and line-graphs of bipartite graphs), or else it has one of two structural faults (star-cutset or 2-join);
since bipartite graphs and line-graphs of bipartite graphs are perfect and since minimal imperfect Berge graphs have neither of the two structural faults; it follows that every square-free Berge graph is perfect.

The Strong Perfect Graph Theorem

In May 2002, Maria Chudnovsky and Paul Seymour announced that they, building on earlier joint work with Neil Robertson and Robin Thomas, had completed the proof of the Strong Perfect Graph Conjecture. The four joint authors presented their work at a workshop held from October 30 to November 3, 2002 at the American Institute of Mathematics in Palo Alto, California and published the 178-page paper in 2006. Their structural theorem asserts that
every Berge graph either belongs to one of five basic classes, namely, or else it has one of four structural faults, namely,
since all graphs in the five basic classes graphs are perfect, since minimal imperfect Berge graphs have neither of the first three structural faults and since -- as Chudnovsky, Robertson, Seymour, and Thomas also prove in their 148-page paper -- an imperfect Berge graph with the smallest number of vertices has no balanced skew partition, it follows that every Berge graph is perfect.

Since all double split graphs are easily seen to admit skew partitions (even though only rarely balanced skew partitions), an easy corollary of the structural theorem asserts that

every Berge graph either belongs to one of four basic classes, namely, or else it has one of four structural faults, namely,
Furthermore, Maria Chudnovsky (Berge Trigraphs, Journal of Graph Theory 53 (2006), 1--55) showed that an even stronger asertion remains valid: M-joins can be dropped.

References

C. Berge and J.L. Ramírez-Alfonsín, Origins and genesis, in: Perfect Graphs (J.L. Ramírez-Alfonsín and B.A. Reed, eds.), Wiley, 2001, pp. 1--12.

M. Burlet and J.-P. Uhry, Parity graphs, in: Topics on perfect graphs (C. Berge and V. Chvátal, eds.) North-Holland Mathematics Studies, 88. Annals of Discrete Mathematics, 21. North-Holland Publishing Co., Amsterdam-New York, 1984, pp. 253--277

M. Chudnovsky, N. Robertson, P.D. Seymour, and R.Thomas, The strong perfect graph theorem, Ann. Math. 164 (2006), 51--229

V. Chvátal, Star-cutsets and perfect graphs, J. Combin. Theory Ser. B 39 (1985), 189--199.

V. Chvátal and N. Sbihi, Recognizing claw-free perfect graphs, J. Combin. Theory Ser. B 44 (1988), 154--176.

M. Conforti, G. Cornuéjols, and K. Vušković, Square-Free Perfect Graphs, J. Combin. Theory Ser. B 90 (2004), 257--307.

G. Cornuéjols and W.H. Cunningham, Compositions for perfect graphs, Discrete Math. 55 (1985), 245--254.

L. Lovász, Normal hypergraphs and the perfect graph conjecture , Discrete Math. 2 (1972), 253--267.

P.D. Seymour, Decomposition of regular matroids, J. Combin. Theory Ser. B 28 (1980), 305--359.

a photograph of Claude Berge

Related pages: