Very rapid mixing of the Glauber dynamics for proper colorings on bounded‐degree graphs
Very rapid mixing of the Glauber dynamics for proper colorings on bounded‐degree graphs
复制标题
非常快速地混合格劳伯动力学，以便在边界度图上进行正确的着色
DOI：
10.1002/rsa.10020
复制
发表时间：
2002
影响因子：
1
通讯作者：
Michael Molloy
中科院分区：
文献类型：
--
作者：
M. Dyer;Catherine S. Greenhill;Michael Molloy
最近的结果表明，当(I)图是无三角形且Δ-正则且颜色数k是小于2Δ的一个小的常数分数时，或(Ii)图具有最大度Δ且k=2Δ时，图着色的Glauber动力学存在最优混合时间。我们推广了这两个结果，证明了当图具有最大度Δ并且颜色数是小于2Δ. 的一个小的恒定分数时，Glauber动力学存在最优混合时间。2002年，20，98-114
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