On randomly colouring locally sparse graphsReportar como inadecuado

On randomly colouring locally sparse graphs - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 Department of Mathematical Sciences Pittsburgh

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 ,p\ with p #x226a 1, this beats the 11Δ -6 bound of Vigoda for general graphs.

Keywords : Counting Colourings Sampling Markov Chains

Autor: Alan Frieze - Juan Vera -

Fuente: https://hal.archives-ouvertes.fr/


Documentos relacionados