Greedy Coloring - Greed Is Not Always Good

Greed Is Not Always Good

A crown graph (a complete bipartite graph K_n,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.