episciences.org_360_20230328194247164
20230328194247164
episciences.org
raphael.tournoy+crossrefapi@ccsd.cnrs.fr
episciences.org
Discrete Mathematics & Theoretical Computer Science
13658050
01
01
2006
Vol. 8
On randomly colouring locally sparse graphs
Alan
Frieze
https://orcid.org/0000000284815615
Juan
Vera
We consider the problem of generating a random qcolouring 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.
01
01
2006
360
National Science Foundation
0200945
https://hal.science/hal00961105v1
10.46298/dmtcs.360
https://dmtcs.episciences.org/360

https://dmtcs.episciences.org/360/pdf

https://dmtcs.episciences.org/360/pdf