Fewer colors for perfect simulation of proper colorings

Given a graph $G$ and color set $\{1,\dots ,k\}$, a $\textit{proper coloring}$isanassignmentofacolortoeachvertexof$G$ such that no two vertices connected by an edge are given the same color. The problem of drawing a proper coloring exactly uniformly from the set of proper colorings is well-studied. Most recently, Bhandari and Chakraborty developed a polynomial expected time randomized algorithm for obtaining such draws when $k>3\mathrm{\Delta }$, where $\mathrm{\Delta }$ is the maximum degree of the graph. Their approach used a bounding chain together with the coupling from the past protocol. Here a new randomized algorithm is presented based upon the randomness recycler protocol introduced by the author and Fill at FOCS 2000. Given $n$ vertices, this method takes $O(n\ln (n))$ expected steps when $k>2.27(\mathrm{\Delta }-1)$ for all $\Delta \geq 2$.