Jerusalem Mathematics Colloquium

 יום חמימי, כ'ט בניסן, תשס"ג
Thursday, 1st May 2003, 4:00 pm
Mathematics Building, Lecture Hall 2

The Jerusalem Mathematics Coloquium is happy to host this year's Erdos Lecture, which is also being held in conjunction with the Spring School on Combinatorics, Topology and Convexity at the Institute for Advanced Study (Feldman Building)

Maria Chudnovsky

"The Strong Perfect Graph Theorem"

Abstract: 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 known as the Strong Perfect Graph Conjecture.

We call graphs containing no induced odd cycles of length greater than three or their complements Berge graphs. A stronger conjecture was made recently by Conforti, Cornuejols and Vuskovic that any Berge graph either belongs to one of a few well understood basic classes or has a decomposition that can not occur in a minimal counterexample to Berge's Conjecture. In joint work with Neil Robertson, Paul Seymour and Robin Thomas we were able to prove this conjecture and consequently the Strong Perfect Graph Theorem.

Maria Chudnovsky is also giving a lecture in the Spring School on Friday, May 2nd, 2003 at 9.15am, entitled "Testing Perfectness".

List of talks, 2002-03
List of talks, 2001-02
List of talks, 2000-01
List of talks, 1998-99
List of talks, 1997-98