The skewed coloring sampling conjecture

Less than 1 year old · traced to

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 ∥n⃗∥1=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

ni≤⌊n2Δ⌋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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.