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 k/sub 0/, and either: (i) k//spl Delta/ < /spl alpha/* /spl ap/ 1.763 and the girth g /spl ges/ 5, or (ii) k//spl Delta/ < /spl beta/* /spl ap/ 1.489 and the girth g /spl ges/ 6. Previous results on this problem applied when k = /spl Omega/(log n), or when k < 11 /spl Delta//6 for general graphs.