Id: arxiv/2603.08259 Url: https://arxiv.org/abs/2603.08259 Tags: math.CO, cs.DS Score: 0 Title: Sampling Colorings with Fixed Color Class Sizes Domain: math.CO Source: arxiv Authors: Aiya Kuchukova, Will Perkins, Xavier Povill Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-03-09 Page: https://delphi.science/r/arxiv/2603.08259 In 1970 Hajnal and Szemerédi proved a conjecture of Erdös that for a graph with maximum degree $Δ$, there exists an equitable $Δ+1$ coloring; that is a coloring where color class sizes differ by at most $1$. In 2007 Kierstand and Kostochka reproved their result and provided a polynomial-time algorithm which produces such a coloring. In this paper we study the problem of approximately sampling uniformly random equitable colorings. A series of works gives polynomial-time sampling algorithms for colorings without the color class constraint, the latest improvement being by Carlson and Vigoda for…