We consider the problem of generating a random q-coloring of a graph G = (V, E). We consider the simple Glauber Dynamics chain. We show that if the maximum degree Delta > c(1) ln n and the girth g > c(2)ln Delta (n = V) for sufficiently large c(1), c(2), then this chain mixes rapidly provided q/Delta > beta, where beta approximate to 1.763 is the root of beta = e(1/beta). For this class of graphs, this beats the 11Delta/6 bound of Vigoda [E. Vigoda, Improved bounds for sampling colorings, Proc 40th Annu IEEE Symp Foundations of Computer Science, 1999, pp. 51-59] for general graphs. We extend the result to random graphs. (C) 2003 Wiley Periodicals, Inc. [References: 14]
展开▼
