All reports by Author Sayantan Chakraborty:

__
TR19-164
| 6th November 2019
__

Siddharth Bhandari, Sayantan Chakraborty#### Improved bounds for perfect sampling of $k$-colorings in graphs

Revisions: 1

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 of $G$. The

distribution of the coloring is perfectly uniform over the set of all proper $k$-colorings; ...
more >>>