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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2006, 8, pp.121-128
Liste complète des métadonnées

Littérature citée [18 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00961105
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mercredi 19 mars 2014 - 14:30:50
Dernière modification le : mercredi 29 novembre 2017 - 10:26:23
Document(s) archivé(s) le : jeudi 19 juin 2014 - 11:36:09

Fichier

dm080107.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

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

Partager

Métriques

Consultations de la notice

149

Téléchargements de fichiers

219