Random colorings of graphs
|Affiliation:||University of Waterloo|
|Room:||Mathematics & Computer Building (MC) 5158|
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.
200 University Avenue West
Waterloo, ON N2L 3G1