Randomly Coloring Random Graphs

We consider the problem of generating a coloring of the random graph G(n,p) uniformly at random using a natural Markov chain algorithm: the Glauber dynamics. We assume that there are beta Delta colors available, where Delta is the maximum degree of the graph, and we wish to determine the least beta = beta(p) such that the distribution is close to uniform in O(n log n) steps of the chain. This problem has been previously studied for G(n,p) in cases where np is relatively small. Here we consider the "dense" cases, where np is an element of [omega In n, n] and omega = omega(n) -> infinity. Our methods are closely tailored to the random graph setting, but we obtain considerably better bounds on beta(p) than can be achieved using more general techniques. (C) 2009 Wiley Periodicals, Inc. Random Struct. Alg., 36, 251-272, 2010