We consider approximate counting of colorings of an n-vertex graph using rapidly mixing Markov chains. It has been shown by Jerrum and by Salas and Sokal that a simple random walk on graph colorings would mix rapidly, provided the number of colors k exceeded the maximum degree $\Delta$ of the graph by a factor of at least 2. We prove that this is not a necessary condition for rapid mixing by considering the simplest case of 5-coloring graphs of maximum degree 3. Our proof involves a computer-assisted proof technique to establish rapid mixing of a new "heat bath" Markov chain on colorings using the method of path coupling. We outline an extension to 7-colorings of triangle-free 4-regular graphs. Since rapid mixing implies approximate counting in polynomial time, we show in contrast that exact counting is unlikely to be possible (in polynomial time). We give a general proof that the problem of exactly counting the number of proper k-colorings of graphs with maximum degree $\Delta$ is $# P$-complete whenever $k\geq 3$ and $\Delta \geq 3$.

The main technique used in algorithm design for approximating #P-hard counting problems is the Markov chain Monte Carlo method. At the heart of the method is the study of the convergence (mixing) rates of particular Markov chains of interest. In this paper we illustrate a new approach to the coupling technique, which we call path coupling, for bounding mixing rates. Previous applications of coupling have required detailed insights into the combinatorics of the problem at hand, and this complexity can make the technique extremely difficult to apply successfully. Path coupling helps to minimize the combinatorial difficulty and in all cases provides simpler convergence proofs than does the standard coupling method. However the true power of the method is that the simplification obtained may allow coupling proofs which were previously unknown, or provide significantly better bounds than those obtained using the standard method. We apply the path coupling method to several hard combinatorial problems, obtaining new or improved results. We examine combinatorial problems such as graph colouring and TWICE-SAT, and problems from statistical physics, such as the antiferromagnetic Potts model and the hard-core lattice gas model. In each case we provide either a proof of rapid mixing where none was known previously, or substantial simplification of existing proofs with consequent gains in the performance of the resulting algorithms.