Sampling Colorings Close to the Maximum Degree: Non-Markovian Coupling and Local Uniformity

Vishesh Jain, Clayton Mizgerd, Eric Vigoda

Sampling graph colorings via local Markov chains is a central problem in approximate counting and Markov chain Monte Carlo (MCMC). We address the problem of sampling a random $k$-c…