Sampling Proper Colorings on Line Graphs Using (1+o(1))Δ Colors

Yulin Wang; Chihao Zhang; Zihan Zhang

doi:10.1145/3618260.3649724

STOC2024顶会

Sampling Proper Colorings on Line Graphs Using (1+o(1))Δ Colors

Yulin Wang, Chihao Zhang, Zihan Zhang

arXiv DOI 出版方

2024年份

3顶会引用

摘要

We prove that the single-site Glauber dynamics for sampling proper q-colorings mixes in OΔ(nlogn) time on line graphs with n vertices and maximum degree Δ when q>(1+o(1))Δ. The main tool in our proof is the matrix trickle-down theorem developed by Abdolazimi, Liu and Oveis Gharan (FOCS, 2021).