On the Probable Performance of Graph coloring Algorithms

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