Polynomial Recognition Algorithm Found

A polynomial algorithm to test whether a graph is Berge was found in November 2002. A paper summarizing the work of two groups-- Chudnovsky and Seymour and Cornuejols, Liu and Vuscovic-- is due to appear in Combinatorica. The algorithm is independent of the proof of the strong perfect graph conjecture.

Back to the main index for Perfect Graphs.