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

https://hal.inria.fr/hal-00961105
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

File

dm080107.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

72

Files downloads

714