Sampling Proper Colorings on Line Graphs Using $(1+o(1))\Delta$ Colors

Yulin Wang, Chihao Zhang, Zihan Zhang

We prove that the single-site Glauber dynamics for sampling proper $q$-colorings mixes in $O_{\Delta }(n\log n)$ time on line graphs with $n$ vertices and maximum degree $\Delta$ when $q>(1+o(1…