The acyclic hero characterization for tournaments
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.
Sources & referencesView supporting material
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
Sign in to submit a solution.
No solutions have been posted yet.