{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-03-09","reactions":{}}