Polynomial-time acyclic k-dicolouring conjecture for tournaments

About 1 year old · traced to

For a tournament TT, let χ⃗a(T)\vec{\chi}_{\rm a}(T) denote its acyclic dichromatic number. A fixed integer k≥3k\geq3 is treated as a constant rather than part of the input.

Tournament acyclic dicolouring algorithm conjecture. For every fixed k≥3k\geq3, it is polynomial-time decidable whether a tournament TT satisfies

χ⃗a(T)≤k.\vec{\chi}_{\rm a}(T)\leq k.

The case k=2k=2 is proved polynomial-time solvable in the paper, whereas the corresponding statement for every fixed k≥3k\geq3 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.