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

07/16/2023

∙

by   Yulin Wang, et al.

∙

0

∙

share

We prove that the single-site Glauber dynamics for sampling proper q-colorings mixes in O_Δ(nlog n) 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).