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 <>
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

  • HAL Id : hal-00961105, version 1

Collections

Citation

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

Share

Metrics

Record views

200

Files downloads

965