Technical Report Number
We define a natural probability distribution over the set of k-colorable graphs on n vertices and study the probable performance of several algorithms on graphs selected from this distribution. The main results are listed below. • We describe an algorithm to determine if a given n vertex graph is k-colorable, which runs in time O(n + m log k), where m is the number of edges. We show that this algorithm can successfully identify almost all random k-colorable graphs for constant or slowly growing values of k. • We show that an algorithm proposed by Brelas, and justified on experimental grounds can successfully k-color almost all random k-colorable graphs for constant or slowly growing values of k. We also describes an efficient implementation, which runs in time O(m log n). • We show that the performance of the well-known greedy algorithm for graph coloring is relatively poor for random k-colorable graphs. In addition to the analytical results, we present experimental data which provide more detailed information on the performance of these algorithms.
Turner, Jonathan S., "On the Probable Performance of Graph coloring Algorithms" Report Number: WUCS-85-07 (1985). All Computer Science and Engineering Research.