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:
“It is the child in man that is the source of his uniqueness and creativeness, and the playground is the optimal milieu for the unfolding of his capacities and talents.”
—Eric Hoffer (1902–1983)
“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)