More on Perfect Graphs

Today I saw Maria Chudnovsky give a talk at Princeton on her new result with Paul Seymour finding a polynomial-time algorithm for testing perfect graphs, a result I mentioned in an earlier post. The algorithm actually tests for Berge graphs which are graphs with no induced odd cycle of length at least five or the complement of such a graph. An earlier result of Chudnovsky, Robertson, Seymour and Thomas showed that a graph is perfect if and only if it is Berge. Otherwise the new algorithm does not use the techniques of the earlier paper.

The algorithm looks for some basic structures that would imply the graph is not Berge. If these structures don't exist then one does a cleaning process that simplifies the search for odd cycles. A cleaning process is described in another paper by Chudnovsky, Cornuéjols, Liu, Seymour and Vuškovic.

While the algorithm will test whether the graph is Berge, it is still open to determine whether a graph had an odd cycle of length at least five.

Chudnovsky's web page now has papers describing all of these results as well as other pointers on perfect graphs.