Randomly Coloring Constant Degree Graphs
Randomly Coloring Constant Degree Graphs
We study a simple Markov chain, known as the Glauber dynamics, for generating a random k-coloring of a n-vertex graph with maximum degree /spl Delta/. We prove that the dynamics converges to a random coloring after O(n log n) steps assuming k /spl ges/ k/sub 0/ for some absolute constant …