Coloring Berge Graphs Using Even Pairs

It is known (from Fonlupt and Uhry) that contracting an even pair in a perfect graph yields a perfect graph with the same chromaticnumber. This idea can be used as the basis for a conceptually simple coloring algorithm.

Contributed by Frédéric Maffray

Back to the main index for Perfect Graphs.