Perfect Graphs

October 11, 2000
12:30 pm - 1:30 pm
Halligan 111
Speaker: Vasek Chvátal, Rutgers University

Abstract

In 1960, Claude Berge introduced the notion of a perfect graph and proposed his famous Strong Perfect Graph Conjecture. Forty years later, the conjecture remains open and perfect graphs have become one of the focal points of graph theory: the bibliography on the subject at http://www.cs.rutgers.edu/~chvatal/perfect/papers.html has well over 500 items. I will talk about the problem of recognizing perfect graphs in polynomial time.