Iterated colorings of graphs. (Q1427472)

Let \(P\) be a property of a set of vertices of a graph (e.g., being a maximal independent set in the graph). An iterated \(P\)-coloring of a graph is one that can be obtained through the following greedy algorithm (called iterated coloring algorithm by the authors): Repeatedly choose a set of vertices with property \(P\), color it with an unused color and delete it. For several properties \(P\), bounds for the maximum and minimum number of colors an iterated \(P\)-coloring can have are given. Some algorithmic issues are discussed as well.