The skewed coloring sampling conjecture

From papers

Let GG be a graph on nn vertices with maximum degree Δ\Delta, and let n=(n1,,nq)\vec{n}=(n_1,\ldots,n_q) satisfy n1=n\|\vec{n}\|_1=n. An n\vec{n}-coloring is a proper coloring with exactly nin_i vertices of color ii.

Skewed sampling conjecture. There should be a polynomial-time algorithm that approximately samples uniformly from the set of n\vec{n}-colorings of GG whenever

nin2Δn_i\leq\left\lfloor\dfrac{n}{2\Delta}\right\rfloor

for every i[q]i\in[q].

The paper presents this as a possible first step toward sampling substantially more skewed colorings, requiring new ideas; no resolution is supplied.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Aiya Kuchukova, Will Perkins and Xavier Povill, “Sampling Colorings with Fixed Color Class Sizes”, arXiv:2603.08259 (2026).

Solutions 0

No solutions have been posted yet.