The acyclic hero characterization for tournaments
Let and be tournaments. A tournament is an acyclic hero if there is a constant such that every -free tournament has acyclic dichromatic number at most . For tournaments , let denote the tournament formed from disjoint copies by orienting every arc from to , and let denote the cyclic composition of three tournaments. Write for the transitive tournament . For every , define
and let be the class of tournaments that occur as subtournaments of some .
The acyclic hero conjecture. A tournament is an acyclic hero if and only if .
The forward implication is proved in the paper, as are several examples of tournaments in that are acyclic heroes. The converse, and hence the characterization, remains open.
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
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.