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.