Iterated colorings of graphs. (Q1427472)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Iterated colorings of graphs. |
scientific article |
Statements
Iterated colorings of graphs. (English)
0 references
14 March 2004
0 references
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.
0 references
independence
0 references
domination
0 references
irredundance
0 references