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 $\Delta$. In the sequential setting…