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)
“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)