Polynomial-time acyclic k-dicolouring conjecture for tournaments
For a tournament , let denote its acyclic dichromatic number. A fixed integer is treated as a constant rather than part of the input.
Tournament acyclic dicolouring algorithm conjecture. For every fixed , it is polynomial-time decidable whether a tournament satisfies
The case is proved polynomial-time solvable in the paper, whereas the corresponding statement for every fixed is posed as an open complexity problem.
References
Primary source
Jørgen Bang-Jensen, Lucas Picasarri-Arrieta and Anders Yeo, “Acyclic dichromatic number of oriented graphs”, arXiv:2511.20246 (2025).
Progress summary
Never refreshed
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.