The Glauber Dynamics for Colourings of Bounded Degree Trees - Lucier, Brendan; Molloy, Mike; Peres, Yuval (International Workshop on Randomization and Computation 2009, 2009)
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 every tree is at most nO(1+∆/(k log∆)). This bound is tight up to the constant factor in the exponent, as evidenced by the complete tree. Our proof uses a weighted canonical paths analysis and a variation of the block dynamics that exploits the differing relaxation times of blocks.