PreprintarXiv licencearXiv
A Hajnal-Szemerédi Theorem for Skewed Colorings
Abstract
The Hajnal-Szemerédi theorem guarantees an equitable (r + 1)-coloring of every graph of maximum degree at most r. We prove a version of this result for more general prescribed color class sizes, subject only to a natural upper bound.
Related
- The Hajnal-Szemerédi theorem in digraphs revisited
- Further bounds in the polynomial Szemerédi theorem
- Szemerédi's theorem with random differences and arithmetic Kakeya
- Multidimensional Szemerédi Theorem for Pairwise Independent Jointly Intersective Polynomials
- Two proofs and a tight Szemerédi--Trotter theorem
BibTeX
@misc{birken2026hajnalszemerédi,
title = {{A Hajnal-Szemerédi Theorem for Skewed Colorings}},
author = {Mathis Birken},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.18629},
eprint = {2609.18629},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.18629},
}
RIS
TY - UNPB
TI - A Hajnal-Szemerédi Theorem for Skewed Colorings
AU - Mathis Birken
PY - 2026
DA - 2026/09/16
PB - arXiv
DO - 10.48550/arxiv.2609.18629
UR - https://arxiv.org/abs/2609.18629
AB - The Hajnal-Szemerédi theorem guarantees an equitable (r + 1)-coloring of every graph of maximum degree at most r. We prove a version of this result for more general prescribed color class sizes, subject only to a natural upper bound.
ER -