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.