The Mixing Time of Glauber Dynamics for Coloring Regular Trees
We consider Metropolis Glauber dynamics for sampling proper q-colorings of the n-vertex complete b-ary tree when 3 <= q <= b/(2 ln b). We give both upper and lower bounds on the mixing time. Our upper bound is n(O(b/log b)) and our lower bound is n(Omega(b/(qlog b))) where the constants implicit in the O() and Omega() notation do not depend upon n, q or b. (C) 2010 Wiley Periodicals, Inc. Random Struct. Alg., 36, 464-476, 2010
mixing time glauber dynamics coloring trees