The Hajnal-Szemerédi theorem in digraphs revisited
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.12207
curl -X POST /api/v1/records/arxiv/2608.12207/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.12207/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'