On approximately counting colorings of small degree graphs

We consider approximate counting of colorings of an n-vertex graph using ra pidly mixing Markov chains. It has been shown by Jerrum and by Salas and So kal that a simple random walk on graph colorings would mix rapidly, provide d 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 maxi mum degree 3. Our proof involves a computer-assisted proof technique to est ablish rapid mixing of a new "heat bath" Markov chain on colorings using th e method of path coupling. We outline an extension to 7-colorings of triang le-free 4-regular graphs. Since rapid mixing implies approximate counting i n polynomial time, we show in contrast that exact counting is unlikely to b e possible (in polynomial time). We give a general proof that the problem o f exactly counting the number of proper k-colorings of graphs with maximum degree Delta is #P-complete whenever k greater than or equal to 3 and Delta greater than or equal to 3.