An extension of path coupling and its application to the Glauber
dynamics of graph colorings.  <P>

A new method for analyzing the mixing time of Markov chains is described.
This method is an extension of path coupling and involved analyzing the
coupling over multiple steps.  The expected behavior of the ocupling at
a certain stopping time is used to bound the expected behavior of the
coupling after a fixed number of steps.  The new method is applied to
analyze the mixing time of the Glauber dynamics for graph colorings.
We show that the Glauber dynamics has O(n log n) mixing time for 
triangle-free D-regular graphs if k colors are used, where k >= (2-a)D
for some small positive constant a.  This is the first proof of an optimal
upper bound for the mixing time of the Glauber dynamics for some values
of k in the range k <= 2D.
 <P>

Appeared in SODA 2000. <P>