Improved Bounds on the Complexity of Graph Coloring

The coloring of random graphs has been the subject of intensive research in the last decades. As a result, the asymptotic behaviour of both the chromatic number and the complexity of the colorability problem are quite well understood. However, the asymptotic results give limited help in predicting the behaviour in specific finite cases. In this paper, we consider the application of the usual backtrack algorithm to random graphs, and analyze the expected size of the search tree as a machine-independent measure of algorithm complexity. With a combination of combinatorial, probabilistic and analytical methods, we derive upper and lower bounds for the expected size of the search tree. Our bounds are much tighter than previous results and thus enable accurate prediction of algorithm runtime.