Greed Is Not Always Good
A crown graph (a complete bipartite graph Kn,n, with the edges of a perfect matching removed) is a particularly bad case for greedy coloring: if the vertex ordering places two vertices consecutively whenever they belong to one of the pairs of the removed matching, then a greedy coloring will use n colors, while the optimal number of colors for this graph is two. There also exist graphs such that with high probability a randomly chosen vertex ordering leads to a number of colors much larger than the minimum. Therefore, it is of some importance in greedy coloring to choose the vertex ordering carefully.
It is NP-complete to determine, for a given graph G and number k, whether there exists an ordering of the vertices of G that forces the greedy algorithm to use k or more colors. In particular, this means that it is difficult to find the worst ordering for G.
Read more about this topic: Greedy Coloring
Famous quotes containing the words greed is and/or greed:
“Greed is all right, by the way... I think greed is healthy. You can be greedy and still feel good about yourself.”
—Ivan F. Boesky (b. 1937)
“Who does not know that kings and rulers sprang from men who were ignorant of God, who assumed because of blind greed and intolerable presumption to make themselves masters of other men, their equals, by means of pride, violence, bad faith, murder, and almost every other kind of crime? Surely the devil drove them on.”
—Pope Gregory VII (c. 1020–1085)