parkol — Exact Uniform Sampling of Graph Colorings

PaRKol (Partial Rejection sampling for K-coloring) is a Python package for drawing exact uniform samples of proper \(k\)-colorings of a graph.

It implements the soft coloring framework, which decomposes the global sampling problem into small independent subproblems via partial rejection sampling (PRS), then solves each subproblem with coupling from the past (CFTP) or other exact samplers. The algorithm is inherently parallelizable and achieves near-linear runtime in the number of vertices.

Installation

pip install parkol

Quick Start

import networkx as nx
from parkol import sample_coloring, verify_coloring

G = nx.petersen_graph()         # 10 vertices, max degree 3
colors = sample_coloring(G, k=5)
print(verify_coloring(G, colors))  # True
print(colors)                      # {0: 3, 1: 5, 2: 1, ...}

Choosing a Method

Pass the method argument to select the sampling algorithm:

colors = sample_coloring(G, k=5)                          # hybrid (default)
colors = sample_coloring(G, k=5, method='prs')            # pure gamma-PRS
colors = sample_coloring(G, k=15, method='cftp_huber')    # Huber CFTP
colors = sample_coloring(G, k=10, method='cftp_bc20')     # BC20 CFTP
colors = sample_coloring(G, k=5, method='nrs')            # naive rejection

Method

Description

Condition

'hybrid'

PRS decomposition + CFTP on components (default, recommended)

\(k > \Delta\)

'prs'

Pure \(\gamma\)-PRS (iterative)

\(k > \Delta\)

'cftp_huber'

Huber (1998) bounding-chain CFTP

\(k > \Delta\)

'cftp_bc20'

Bhandari & Chakraborty (2020) CFTP

\(k > 3\Delta\)

'nrs'

Naive rejection sampling

\(k > \Delta\)

Adaptive Gamma-Sequence

The adaptive option uses a gamma-sequence that encourages the resampling set to split into multiple connected components, enabling parallel processing:

# Adaptive with 8 target components
colors = sample_coloring(G, k=20, adaptive=True, target_components=8)

Reproducibility

Pass a seed for deterministic output:

colors = sample_coloring(G, k=5, seed=42)  # reproducible

API Reference

References

  • S. Moka and A. Vahedi (2026). Uniform Sampling of Proper Graph Colorings via Soft Coloring and Partial Rejection Sampling. Preprint.

  • S. Bhandari and S. Chakraborty (2020). Improved Bounds for Perfect Sampling of k-Colorings in Graphs. Proc. STOC 2020.

  • M. Huber (1998). Perfect Sampling Using Bounding Chains. Ann. Appl. Probab. 14(2), 734–753.

  • H. Guo, M. Jerrum, and J. Liu (2017). Uniform Sampling Through the Lovasz Local Lemma. Proc. STOC 2017, 342–355.