Perfect and locally perfect colorings

We present a new algorithm for coloring perfect graphs and use it to color the parity orderable graphs, a class which strictly contains parity graphs. Also, we modify this algorithm to obtain an O(m² + n) locally perfect coloring algorithm for parity graphs. © 1995 John Wiley & Sons, Inc.