Improved Distributed Algorithms for Random Colorings

Charlie Carlson, Daniel Frishberg, Eric Vigoda

We study distributed versions of Markov Chain Monte Carlo (MCMC) algorithms for generating random $k$-colorings of an input graph with maximum degree $\hat{I}”$. In the sequential settin…