1
views
0
recommends
+1 Recommend
0 collections
0
shares
• Record: found
• Abstract: found
• Article: found
Is Open Access

# Perfect Sampling of graph $$k$$-colorings for $$k=o(\Delta^2)$$

Preprint

,

Bookmark
There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

### Abstract

We give an algorithm for perfect sampling from the uniform distribution on proper $$k$$-colorings of graphs of maximum degree $$\Delta$$, which, for $$\Delta \in [17, \log n]$$, terminates with a sample in expected time $$\mathrm{poly}(n)$$ time whenever $$k >\frac{2e\Delta^2}{\log \Delta}$$ (here, $$n$$ is the number of vertices in the graph). To the best of our knowledge, this is the first perfect sampling algorithm for proper $$k$$-colorings that provably terminates in expected polynomial time while requiring only $$k=o(\Delta^2)$$ colors in general. Inspired by the \emph{bounding chain} approach pioneered independently by H\"aggstr\"om \& Nelander~(Scand. J. Statist., 1999) and Huber~(STOC 1998) (who used the approach to give a perfect sampling algorithm requiring $$k >\Delta^2 + 2\Delta$$ for its expected running time to be a polynomial), our algorithm is based on a novel bounding chain for the coloring problem.

### Most cited references6

• Record: found

### An interruptible algorithm for perfect sampling via Markov chains

(1998)
Bookmark
• Record: found

### Exact sampling and approximate counting techniques

(1998)
Bookmark
• Record: found

### Uniform sampling through the Lovasz local lemma

(2017)
Bookmark

### Author and article information

###### Journal
23 September 2019
###### Article
1909.10323