Fewer colors for perfect simulation of proper colorings

Abstract

Given a graph $G$ and color set $\{1,\dots ,k\}$, a $\text{proper coloring}$ is an assignment of a color to each vertex of $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\hat{I}”$, where $\hat{I}”$ 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(\hat{I}”-1)$ for all $\hat{I}”\ge 2$.

The paper contained an error in Lemma 5. The weight of the recycled state is $(k_v-1)/k_v$, which depends on the neighboring colors in the state. That prevents the output of the algorithm from being uniform