The analysis of a list-coloring algorithm on a random graph

We introduce a natural k-coloring algorithm and analyze its performance on random graphs with constant expected degree c (G(n,p=c/n)) for k = 3 our results imply that almost all graphs with n vertices and 1.923 n edges are S-colorable. This improves the lower bound on the threshold for random 3-colorability significantly and settles the last case of a long-standing open question of Bollobas [5]. We also provide a tight asymptotic analysis of the algorithm. We show that for all k greater than or equal to 3, if c less than or equal to k ln k - 3/2k then the algorithm almost surely succeeds, while for any epsilon > 0, and k sufficiently large, if c greater than or equal to (1 + epsilon)k In if then the algorithm almost surely fails. The analysis is based on the use of differential equations to approximate the mean path of certain Markov chains.