combinatorics / Graph theory

Treglown's equitable acyclic colouring conjecture

Treglown conjectured, in a complementary form, that for every positive integer $k$ every digraph $D$ with $\min\{d^+(v), d^-(v)\} \le k-1$ for all $v$ has an equitable acyclic $k$-colouring. This implies the acyclic colouring versions of the Hajnal-Szemeredi theorem for digraphs proved by Czygrinow, DeBiasio, Kierstead and Molla, which in turn imply the original Hajnal-Szemeredi theorem for graphs. Proved: a short reduction shows the conjecture follows directly from the original Hajnal-Szemeredi theorem, and a modification of it gives a polynomial-time algorithm for finding such a colouring.

15Significance / 100
1Frontier events
0Verification tasks
0Recorded attempts

Temporal state

Current frontier

No reconciled state yet.

Append-only history

Frontier timeline

combinatoricsAug 12, 2026Significance 15/100Registry: unreviewed

Treglown's equitable acyclic colouring conjecture

Prior state unknownproved

The honest reading, which the paper gives itself: the reduction is implicit in earlier work of Aboulker, Oijid, Petit, Rocton and Simon, and the model itself surfaced that reference when asked about originality. So this establishes the conjecture and supplies a polynomial-time algorithm, while the underlying idea is a rediscovery rather than a first. It is a striking record of a model producing an argument and the…

SourceReplayReproducedFormal proofStatement auditExternal checkExpert reviewPeer review

Research memory

Claims and attempts

Scoped claims

Source authenticated

Treglown conjectured, in a complementary form, that for every positive integer $k$ every digraph $D$ with $\min\{d^+(v), d^-(v)\} \le k-1$ for all $v$ has an equitable acyclic $k$-colouring. This implies the acyclic colouring versions of the Hajnal-Szemeredi theorem for digraphs proved by Czygrinow, DeBiasio, Kierstead and Molla, which in turn imply the original Hajnal-Szemeredi theorem for graphs. Proved: a short reduction shows the conjecture follows directly from the original Hajnal-Szemeredi theorem, and a modification of it gives a polynomial-time algorithm for finding such a colouring.

The honest reading, which the paper gives itself: the reduction is implicit in earlier work of Aboulker, Oijid, Petit, Rocton and Simon, and the model itself surfaced that reference when asked about originality. So this establishes the conjecture and supplies a polynomial-time algorithm, while the underlying idea is a rediscovery rather than a first. It is a striking record of a model producing an argument and then correcting the novelty claim made for it.

Recorded attempts

Evidence graph

Connected research record

No public relationships recorded yet.