Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR04-009 | 22nd January 2004 00:00

Randomly coloring constant degree graphs

RSS-Feed




TR04-009
Authors: Martin Dyer, Alan Frieze, Thomas P. Hayes, Eric Vigoda
Publication: 2nd February 2004 22:25
Downloads: 2915
Keywords: 


Abstract:

We study a simple Markov chain, known as the Glauber dynamics, for generating a random <i>k</i>-coloring of a <i>n</i>-vertex graph with maximum degree &Delta;. We prove that the dynamics converges to a random coloring after <i>O</i>(<i>n</i> log <i>n</i>) steps assuming <i>k</i> &ge; <i>k</i><sub>0</sub> for some absolute constant <i>k</i><sub>0</sub>, and either:
(i) <i>k</i>/&Delta; > &alpha;<sup>*</sup> = 1.763... and the girth <i>g</i> &ge; 5, or
(ii) <i>k</i>/&Delta; > &beta;<sup>*</sup> = 1.489... and the girth <i>g</i> &ge; 6.
Previous results on this problem applied when <i>k</i> = &Omega;(log <i>n</i>), or when <i>k</i> > 11&Delta;/6 for general graphs.



ISSN 1433-8092 | Imprint