%0 Journal Article
%T On randomly colouring locally sparse graphs
%A Alan Frieze
%A Juan Vera
%J Discrete Mathematics & Theoretical Computer Science
%D 2006
%I Discrete Mathematics & Theoretical Computer Science
%X We consider the problem of generating a random q-colouring of a graph G=(V,E). We consider the simple Glauber Dynamics chain. We show that if for all v ¡Ê V the average degree of the subgraph H v induced by the neighbours of v ¡Ê V is  ¦¤ where ¦¤ is the maximum degree and ¦¤>c 1 ln n then for sufficiently large c 1, this chain mixes rapidly provided q/¦¤>¦Á, where ¦Á¡Ö 1.763 is the root of ¦Á = e {1/¦Á}. For this class of graphs, which includes planar graphs, triangle free graphs and random graphs G {n,p} with p   1, this beats the 11¦¤/6 bound of Vigoda for general graphs.
%U http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/496