Tutte seminar - Juan Vera

Random colorings of graphs

Abstract:

We consider the problem of generating a colouring of the graph G uniformly at random using a natural Markov chain algorithm: the Glauber dynamics. We survey results on generating random colorings for general graphs and present improved results on random colorings of planar graphs.

Joint work with Nayantara Bhatnagar, Thomas Hayes and Eric Vigoda.