Sequential colorings and perfect graphs

We study a variant of a sequential algorithm for coloring the vertices of a graph, using bichromatic exchanges, and exhibit a class of graphs which ha ve the property that there is an ordering of the vertices such that this al gorithm provides an optimal coloring for each induced ordered subgraph. The se graphs are perfect and generalize several well-known classes of perfect graphs such as line-graphs of bipartite graphs or triangulated graphs. (C) 1999 Elsevier Science B.V. All rights reserved.