Optimal Ordering
The vertices of any graph may always be ordered in such a way that the greedy algorithm produces an optimal coloring. For, given any optimal coloring in which the smallest color set is maximal, the second color set is maximal with respect to the first color set, etc., one may order the vertices by their colors. Then when one uses a greedy algorithm with this order, the resulting coloring is automatically optimal. More strongly, perfectly orderable graphs (which include chordal graphs, comparability graphs, and distance-hereditary graphs) have an ordering that is optimal both for the graph itself and for all of its induced subgraphs. However, finding an optimal ordering for an arbitrary graph is NP-hard (because it could be used to solve the NP-complete graph coloring problem), and recognizing perfectly orderable graphs is also NP-complete. For this reason, heuristics have been used that attempt to reduce the number of colors while not guaranteeing an optimal number of colors.
Read more about this topic: Greedy Coloring
Famous quotes containing the words optimal and/or ordering:
“In the most desirable conditions, the child learns to manage anxiety by being exposed to just the right amounts of it, not much more and not much less. This optimal amount of anxiety varies with the child’s age and temperament. It may also vary with cultural values.... There is no mathematical formula for calculating exact amounts of optimal anxiety. This is why child rearing is an art and not a science.”
—Alicia F. Lieberman (20th century)
“Make gracious attempts at sanctifying Jenny,
Supply cosmetics for the ordering of her frame,
Think of her as Leda, as a goddess,
Emptying a smile on Redkey, Indiana.”
—Allen Tate (1899–1979)