On randomly colouring locally sparse graphs - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Discrete Mathematics and Theoretical Computer Science Année : 2006

On randomly colouring locally sparse graphs

Résumé

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.
Fichier principal
Vignette du fichier
dm080107.pdf (118.38 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00961105 , version 1 (19-03-2014)

Identifiants

Citer

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

Collections

TDS-MACS
73 Consultations
874 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More