A MORE RAPIDLY MIXING MARKOV-CHAIN FOR GRAPH COLORINGS

We define a new Markov chain on (proper) k-colorings of graphs, and re late its convergence properties to the maximum degree Delta of the gra ph. The chain is shown to have bounds on convergence time appreciably better than those for the well-known Jerrum/Salas-Sokal chain in most circumstances. For the case k=2 Delta, we provide a dramatic decrease in running time. We also show improvements whenever the graph is regul ar, or fewer than 3 Delta colors are used. The results are established using the method of path coupling. We indicate that our analysis is t ight by showing that the couplings used are optimal in a sense which w e define. (C) 1998 John Wiley & Sons, Inc.