Skip to Main content Skip to Navigation
Journal articles

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 #x226a Δ where Δ is the maximum degree and Δ >c_1\ln n then for sufficiently large c_1, this chain mixes rapidly provided q/Δ >α , where α #x2248 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 #x226a 1, this beats the 11Δ /6 bound of Vigoda for general graphs.
Document type :
Journal articles
Complete list of metadata

Cited literature [18 references]  Display  Hide  Download
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s Connect in order to contact the contributor
Submitted on : Wednesday, March 19, 2014 - 2:30:50 PM
Last modification on : Wednesday, November 29, 2017 - 10:26:23 AM
Long-term archiving on: : Thursday, June 19, 2014 - 11:36:09 AM


Files produced by the author(s)




Alan Frieze, Juan Vera. On randomly colouring locally sparse graphs. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2006, Vol. 8, pp.121-128. ⟨10.46298/dmtcs.360⟩. ⟨hal-00961105⟩



Record views


Files downloads