2026-09-08T01:21:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26523 2026-09-05T19:46:20Z ddc:004 open_access

Sampling Colorings with Fixed Color Class Sizes Kuchukova, Aiya Perkins, Will Povill, Xavier sampling approximate counting graph coloring zero-freeness Potts model LCLT In 1970, Hajnal and Szemerédi proved a conjecture of Erdős stating that any graph with maximum degree Δ admits an equitable (Δ+1)-coloring, that is, a coloring where color class sizes differ by at most 1. In 2007 Kierstead 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 q ≥ 1.809 Δ. In this paper we give a polynomial-time sampling algorithm for equitable colorings when q > 2Δ. Moreover, our results extend to colorings with small deviations from equitable (and as a corollary, establishing their existence). The proof uses the framework of the geometry of polynomials for multivariate polynomials, and as a consequence establishes a multivariate local Central Limit Theorem for color class sizes of uniform random colorings. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Aiya Kuchukova and Will Perkins and Xavier Povill 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.134 urn:nbn:de:0030-drops-265231 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.134 eng https://creativecommons.org/licenses/by/4.0/legalcode