Metraipolis › archive › dc_c45aea99df38
A square-root law for equitable coloring — arXiv:2609.25041
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.25041
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-08T15:55:44.182Z
- SHA-256 of the archived text
7a2283ceb546d3eedcd3bff8f527e4d91c98bca39fe42159a6098d6e90e485c6- Stable URL of this page
https://metraipolis.com/documento/dc_c45aea99df38
How to cite
A square-root law for equitable coloring — arXiv:2609.25041 — arXiv (en), https://arxiv.org/abs/2609.25041 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_c45aea99df38 (Metraipolis archive dc_c45aea99df38, sha256 7a2283ceb546d3eedcd3bff8f527e4d91c98bca39fe42159a6098d6e90e485c6)
BibTeX
@misc{dcc45aea99df38,
title = {A square-root law for equitable coloring — arXiv:2609.25041},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.25041},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_c45aea99df38; sha256 7a2283ceb546d3eedcd3bff8f527e4d91c98bca39fe42159a6098d6e90e485c6},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.25041. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
An equitable $k$-coloring of a graph partitions its vertex set into $k$ independent sets whose sizes differ by at most one; the least such $k$ is the equitable chromatic number $\chie(G)$. Every known bound on $\chie$ valid for all graphs, beginning with the Hajnal--Szemerédi theorem, is linear in the maximum degree $\Delta$, and the star $K_{1,\Delta}$, for which $\chie=\ceil{\Delta/2}+1$, shows that no general bound below $\Delta/2$ exists. We prove that this obstruction is a shortage of vertices rather than an effect of the degree: every graph with $|V(G)|\ge3\chi(G)\Delta$ satisfies $\chie(G)=O\bigl(\chi(G)^{3/2}\sqrt{\Delta/\ln\Delta}\bigr)$ throughout the range $\chi(G)\le(\Delta/\ln\Delta)^{1/3}$, so that for graphs of large order the degree enters only through $\sqrt{\Delta/\ln\Delta}$, with the chromatic number governing the rest. For each fixed $\ell$, $\ell$-colorable graphs of sufficiently large order satisfy $\chie\le\bigl(2\sqrt2\,\ell\sqrt{\ell-1}+o(1)\bigr)\sqrt{\Delta/\ln\Delta}$, while a probabilistic construction supplies graphs of arbitrarily large order, bipartite when $\ell=2$, with $\chie\ge\tfrac13\sqrt{(\ell-1)\Delta/\ln\Delta}$: the order of growth $\Theta\bigl(\sqrt{\Delta/\ln\Delta}\bigr)$ is exact for every fixed chromatic number, and the extremal constant is determined up to a factor $O(\chi(G))$. All upper bounds are constructive, and a prescribed-anchor variant of the construction produces equitable colorings of bipartite graphs with $O(\sqrt\Delta)$ colors in optimal linear time.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-23 in math.CO).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2609.25041 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-08T15:16:21.653Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-23?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).