On randomly colouring locally sparse graphs

Abstract

We consider the problem of generating a random q-colouring of a graph G=(V,E). We consider the simple Glauber Dynamics chain. We show that if for all v ∈ V the average degree of the subgraph H v induced by the neighbours of v ∈ V is ≪Δ where Δ is the maximum degree and Δ>c 1 ln n then for sufficiently large c 1, this chain mixes rapidly provided q/Δ>α, where α≈ 1.763 is the root of α = e {1/α}. For this class of graphs, which includes planar graphs, triangle free graphs and random graphs G {n,p} with p ≪ 1, this beats the 11Δ/6 bound of Vigoda for general graphs.