The Glauber Dynamics for Colourings of Bounded Degree Trees - Lucier, Brendan; Molloy, Mike (SIAM (Society for Industrial and Applied Mathematics) Journal on Discrete Mathematics 2011, 2010)
We study the Glauber dynamics Markov chain for k-colourings of trees with maximum degree ∆. For k >= 3, we show that the mixing time on the complete tree is nƟ(1+/(k log ∆)). For k >= 4 we extend our analysis to show that the mixing time on any tree is at most nO(1+/(k log ∆)). Our proof uses a weighted canonical paths analysis and introduces a variation of the block dynamics that exploits the di ffering relaxation times of blocks.