Technical Report Number
We describe a simple and efficient heuristic algorithm for the graph coloring problem and show that for all k greater or equal to 1, it finds an optimal coloring for almost all k-colorable graphs. We also show that an algorithm proposed by Brelaz and justified on experimental grounds optimally colors almost all k-O(n+m logk) time when n is the number of vertices and m the number of edges. The new implementation of Brelaz's algorithm runs an O(mlogn) time. We observe that the popular greedy heuristic works poorly on k-colorable graphs.
Turner, Jonathan S., "Almost All k-Colorable Graphs are easy to color" Report Number: WUCS-86-02 (1986). All Computer Science and Engineering Research.