Discrete Mathematics & Theoretical Computer Science, Vol 8 (2006)

Font Size:  Small  Medium  Large

On randomly colouring locally sparse graphs

Alan Frieze, Juan Vera


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