Friday, June 6, 2008
3:30 pm, MC 5158

Juan Vera
Dept. of Management Sciences, University of Waterloo

Random colorings of graphs

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.