Very rapid mixing of the Glauber dynamics for proper colorings on bounded-degree graphs

Recent results have shown that the Glauber dynamics for graph colorings has optimal mixing time when (i) the graph is triangle‐free and Δ‐regular and the number of colors k is a small constant fraction smaller than 2Δ, or (ii) the graph has maximum degree Δ and k=2Δ. We extend both these results to...

Full description

Saved in:
Bibliographic Details
Published in:Random structures & algorithms 2002-01, Vol.20 (1), p.98-114
Main Authors: Dyer, Martin, Greenhill, Catherine, Molloy, Mike
Format: Article
Language:English
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Recent results have shown that the Glauber dynamics for graph colorings has optimal mixing time when (i) the graph is triangle‐free and Δ‐regular and the number of colors k is a small constant fraction smaller than 2Δ, or (ii) the graph has maximum degree Δ and k=2Δ. We extend both these results to prove that the Glauber dynamics has optimal mixing time when the graph has maximum degree Δ and the number of colors is a small constant fraction smaller than 2Δ. © 2002 John Wiley & Sons, Inc. Random Struct. Alg., 20, 98–114, 2002
ISSN:1042-9832
1098-2418
DOI:10.1002/rsa.10020