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.

## No comments:

## Post a Comment