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

Yulin Wang; Chihao Zhang; Zihan Zhang

doi:10.1145/3618260.3649724

STOC2024Top-tier venue

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

Yulin Wang, Chihao Zhang, Zihan Zhang

arXiv DOI Publisher

2024Year

3Top-tier citations

Abstract

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).