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:
“The point is, ladies and gentlemen, that greed, for lack of a better word, is good. Greed is right. Greed works. Greed clarifies, cuts through, and captures the essence of the evolutionary spirit.”
—Stanley Weiser, U.S. screenwriter, and Oliver Stone. Gordon Gekko (Michael Douglas)
“It’s not greed and ambition that makes wars—it’s goodness. Wars are always fought for the best of reasons, for liberation or manifest destiny, always against tyranny and always in the best interests of humanity. So far this war, we’ve managed to butcher some 10,000,000 people in the interest of humanity. The next war, it seems we’ll have to destroy all of man in order to preserve his damn dignity.”
—Paddy Chayefsky (1923–1981)