Perfect graphs can be recognised in polynomial time

You need to know: Polynomial-time algorithms, 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, big O notation.

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. The problem of perfect graph recognition is: given a graph as an input, determine whether it is perfect or not.

The Theorem: On 26th February 2003, Maria Chudnovsky, Gérard Cornuéjols, Xinming Liu, Paul Seymour, and Kristina Vušković submitted to Combinatorica a paper in which they proved that the problem of perfect graph recognition for n-vertex graphs can be solved in time .

Short context: An odd hole is a cycle of odd length and odd antihole is the complement of odd hole. A graph G is Berge if it does not contain an odd hole or an odd antihole as an induced subgraph. The Theorem in fact provides an algorithm for recognising Begre graphs. However, by an earlier result of  Chudnovsky, Robertson, Seymour, and Thomas, a graph G is perfect if and only if it is Begre. This gives the first polynomial-time algorithm for recognising perfect graphs.

Links: The original paper is available here.

Go to the list of all theorems