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)
“Seeing then that truth consisteth in the right ordering of names in our affirmations, a man that seeketh precise truth had need to remember what every name he uses stands for, and to place it accordingly, or else he will find himself entangled in words, as a bird in lime twigs, the more he struggles, the more belimed.”
—Thomas Hobbes (1588–1679)