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 word greed:
“To-day ... when material prosperity and well earned ease and luxury are assured facts from a national standpoint, woman’s work and woman’s influence are needed as never before; needed to bring a heart power into this money getting, dollar-worshipping civilization; needed to bring a moral force into the utilitarian motives and interests of the time; needed to stand for God and Home and Native Land versus gain and greed and grasping selfishness.”
—Anna Julia Cooper (1859–1964)