on randomly colouring locally sparse graphs

on randomly colouring locally sparse graphs

;Alan Frieze;Juan Vera
Proteins 2006 Vol. 8 pp. -
5
frieze2006discreteon

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.

Keywords

Citation

ID: 225397
Ref Key: frieze2006discreteon
Use this key to autocite in SciMatic or Thesis Manager

References

Blockchain Verification

Account:
NFT Contract Address:
0x95644003c57E6F55A65596E3D9Eac6813e3566dA
Article ID:
225397
Unique Identifier:
Network:
Scimatic Chain (ID: 481)
Loading...
Blockchain Readiness Checklist
Authors
Abstract
Journal Name
Year
Title
5/5
Creates 1,000,000 NFT tokens for this article
Token Features:
  • ERC-1155 Standard NFT
  • 1 Million Supply per Article
  • Transferable via MetaMask
  • Permanent Blockchain Record
Blockchain QR Code
Scan with Saymatik Web3.0 Wallet

Saymatik Web3.0 Wallet