The strong perfect graph conjecture is true: all Berge graphs are perfect

You need to know: Basic graph theory: graph, size of a graph (number of its vertices), induced subgraph, complete sugraph, cycle, length of the cycle, complement of a graph, chromatic number of a graph.

Background: A graph G is perfect if for every induced subgraph H, the chromatic
number of H equals to the size of the largest complete subgraph of H. An odd hole is a cycle of odd length n\geq 5 and odd antihole is the complement of odd hole.

The Theorem: On 4th December 2002, Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas submitted to arxiv a paper in which they proved that a graph G is perfect if and only if it does not contain an odd hole or an odd antihole as an induced subgraph.

Short context: In 1961, Berge observed that every perfect graph G does not contain an odd hole or an odd antihole, and conjectured that the converse is true. This conjecture became known as the strong perfect graph conjecture and attracted a lot of attention. Graphs with no odd hole or antihole got the name Berge graphs and the conjecture then states that all Berge graphs are perfect (which implies that the perfect graphs and the Berge graphs define the same class of graphs). The Theorem proves this conjecture and have got the name strong perfect graph theorem. The proof of the strong perfect graph theorem won for its authors several prizes including the 2009 Fulkerson Prize.

Links: Free arxiv version of the original paper is here, journal version is here. See also Section 6.4 of this book for an accessible description of the Theorem.

Go to the list of all theorems

Leave a comment