On randomly colouring locally sparse graphs
Alan Frieze, Juan Vera
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 Hv induced by the neighbours of v ∈ V is ≪Δ where Δ is the maximum degree and Δ>c1ln n then for sufficiently large c1, 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.
Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page