DROPS

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2026.134

Sampling Colorings with Fixed Color Class Sizes

Authors: Aiya Kuchukova, Will Perkins, and Xavier Povill

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract

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.

Cite as

Aiya Kuchukova, Will Perkins, and Xavier Povill. Sampling Colorings with Fixed Color Class Sizes. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 134:1-134:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{kuchukova_et_al:LIPIcs.ICALP.2026.134,
  author =	{Kuchukova, Aiya and Perkins, Will and Povill, Xavier},
  title =	{{Sampling Colorings with Fixed Color Class Sizes}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{134:1--134:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.134},
  URN =		{urn:nbn:de:0030-drops-265231},
  doi =		{10.4230/LIPIcs.ICALP.2026.134},
  annote =	{Keywords: sampling, approximate counting, graph coloring, zero-freeness, Potts model, LCLT}
}

Search Results

Documents authored by Povill, Xavier

Sampling Colorings with Fixed Color Class Sizes

Abstract

Cite as

Thanks for your feedback!

Could not send message