A graph is called perfect if for every induced subgraph the size of its largest clique equals the minimum number of colors needed to color its vertices. In 1960's Claude Berge made a conjecture that has become one of the most well-known open problems in graph theory: any graph that contains no induced odd cycles of length greater than three or their complements is perfect. This conjecture is know as the Strong Perfect Graph Conjecture.
We call graphs containing no induced odd cycles of length greater than three or their complements Berge graphs. Some classic examples of perfect graphs are bipartite graphs, complements of bipartite graphs, line graphs of bipartite graphs, and their complements. It has been conjectured that any Berge graph either belongs to one of these four basic classes or can be decomposed in certain ways into smaller basic pieces. Recently we have been able to prove a statement similar to that -- except that we need five basic classes instead of four -- and consequently, the Strong Perfect Graph Theorem.
This is joint work with Neil Robertson, Paul Seymour, and Robin Thomas.