The skewed coloring sampling conjecture
The skewed coloring sampling conjecture
Let be a graph on vertices with maximum degree , and let satisfy . An -coloring is a proper coloring with exactly vertices of color .
Skewed sampling conjecture. There should be a polynomial-time algorithm that approximately samples uniformly from the set of -colorings of whenever
for every .
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
Sign in to submit a solution.
No solutions have been posted yet.