全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...

On randomly colouring locally sparse graphs

Full-Text   Cite this paper   Add to My Lib

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 Δ where Δ is the maximum degree and Δ>c 1 ln n then for sufficiently large c 1, this chain mixes rapidly provided q/Δ>α, where α≈ 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 1, this beats the 11Δ/6 bound of Vigoda for general graphs.

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133