Id: arxiv/2608.12207 Url: https://arxiv.org/abs/2608.12207 Tags: math.CO Score: 0 Title: The Hajnal-Szemerédi theorem in digraphs revisited Domain: math.CO Source: arxiv Authors: Yufei Chang, Louis DeBiasio, H. A. Kierstead, Shuo Wei, Jin Yan Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-08-12 Page: https://delphi.science/r/arxiv/2608.12207 The Hajnal--Szemerédi theorem states that every graph with $Δ(G)\le 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…