Random sampling of 3-colorings in Z(2)

We consider the problem of uniformly sampling proper 3-colorings of an m X n rectangular region of Z(2). We show that the single-site "Glauber-dynamics" Markov chain is rapidly mixing. Our result complements an earlier result of Luby, Randall, and Sinclair, which demonstrates rapid mixing when there is a fixed boundary (whose color cannot be changed). (C) 2004 Wiley Periodicals, Inc