Abstract

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.