Assuming that a coloring has been generated using the greedy coloring, it follows that for colors c[2] > c[1] every vertex with color c[2] is joined by an edge to some vertex of color c[1]. However, the converse is not true. If the vertices are rearranged so that the vertices of color c[2] precede those of color c[1] and the greedy algorithm is applied, it is possible that some of the vertices from the c[1] set will receive the same color as those in c[2]. An accumulation of such partition changes may result in a reduced coloring.
On random graphs the algorithm does not perform as well as TABU or semi-exhaustive independent set approaches. It does offer some improvements when combined with these. On k-colorable graphs it seems quite effective, and offers a robustness over a wide range of k,n,p values the other algorithms seem not to have. In particular, we will provide evidence that one setting of parameters seems to be ``near best'' over most classes of graphs. Evidence in TR92-07 indicates that graphs in the classes we consider that are harder for this algorithm are also harder for TABU and semi-exhaustive independent set approaches. Thus, the number of iterations required gives a natural measure of difficulty of the graphs, independent of machine characteristics and many details of implementation.
In this paper we explore the range of k-colorable graphs with this algorithm.
These results were presented at the Second DIMACS Challenge on Cliques, Coloring, and Satisfiability. Paper Preprint.
A set of tests using the DIMACS bench mark set for graph coloring, are presented in appendices one, two and three, Additional results, including what it takes to achieve success on the flat1000_60_0.col graph, can be found in the full paper.