Randomly coloring sparse random graphs with fewer colors than the maximum degree

We analyze Markov chains for generating a randomk‐coloring of a random graphGn,d/n. When the average degreedis constant, a random graph has maximum degreeΘ(logn/log logn), with high probability. We show that, with high probability, an efficient procedure can generate an almost uniformly randomk‐coloring whenk=Θ(log logn/log log logn), i.e., with many fewer colors than the maximum degree. Previous results hold for a more general class of graphs, but always require more colors than the maximum degree.