The Hajnal-Szemerédi theorem in digraphs revisited
Abstract
The Hajnal--Szemerédi theorem states that every graph with Δ(G)≤ k−1 admits an equitable k-coloring. Using a reduction implicit in Aboulker, Oijid, Petit, Rocton, and Simon (which itself builds on the literature surrounding feedback arc sets), we prove that this theorem is equivalent to each of four digraph analogues guaranteeing equitable acyclic k-colorings under various degree conditions. A minor modification of the proof method in makes the construction algorithmic, so the equitable acyclic coloring guaranteed by these statements can be found in polynomial time. The same reduction shows that the Ore-type Hajnal--Szemerédi theorem is equivalent to its four digraph analogues. These equivalences settle the conjecture of Treglown that every n-vertex digraph with r| n and δmax(D)≥(1−1/r)n contains a Tr-factor, answer a question of Molla and Treglown by determining the exact Ore-type threshold for Tr-factors, and recover the directed Hajnal--Szemerédi theorems of Czygrinow, DeBiasio, Kierstead, and Molla as immediate corollaries of this reduction. We also discuss related problems for oriented graphs which do not follow immediately from the reduction mentioned above.
Related
- A Hajnal-Szemerédi Theorem for Skewed Colorings
- 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{chang2026hajnalszemerédi,
title = {{The Hajnal-Szemerédi theorem in digraphs revisited}},
author = {Yufei Chang and Louis DeBiasio and H. A. Kierstead and Shuo Wei and Jin Yan},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2608.12207},
eprint = {2608.12207},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.12207},
}
RIS
TY - UNPB
TI - The Hajnal-Szemerédi theorem in digraphs revisited
AU - Yufei Chang
AU - Louis DeBiasio
AU - H. A. Kierstead
AU - Shuo Wei
AU - Jin Yan
PY - 2026
DA - 2026/10/12
PB - arXiv
DO - 10.48550/arxiv.2608.12207
UR - https://arxiv.org/abs/2608.12207
AB - The Hajnal--Szemerédi theorem states that every graph with Δ(G)≤ k−1 admits an equitable k-coloring. Using a reduction implicit in Aboulker, Oijid, Petit, Rocton, and Simon (which itself builds on the literature surrounding feedback arc sets), we prove that this theorem is equivalent to each of four digraph analogues guaranteeing equitable acyclic k-colorings under various degree conditions. A minor modification of the proof method in makes the construction algorithmic, so the equitable acyclic coloring guaranteed by these statements can be found in polynomial time. The same reduction shows that the Ore-type Hajnal--Szemerédi theorem is equivalent to its four digraph analogues. These equivalences settle the conjecture of Treglown that every n-vertex digraph with r| n and δ^max(D)≥(1−1/r)n contains a T_r-factor, answer a question of Molla and Treglown by determining the exact Ore-type threshold for T_r-factors, and recover the directed Hajnal--Szemerédi theorems of Czygrinow, DeBiasio, Kierstead, and Molla as immediate corollaries of this reduction. We also discuss related problems for oriented graphs which do not follow immediately from the reduction mentioned above.
ER -