Improved Bounds for Perfect Sampling of $k$-Colorings in Graphs

Siddharth Bhandari, Sayantan Chakraborty

We present a randomized algorithm that takes as input an undirected $n$-vertex graph $G$ with maximum degree $\Delta$ and an integer $k>3\Delta$, and returns a random proper $k$-coloring o…