The acyclic hero characterization for tournaments

Let TT and HH be tournaments. A tournament is an acyclic hero if there is a constant cHc_H such that every HH-free tournament has acyclic dichromatic number at most cHc_H. For tournaments H1,H2H_1,H_2, let H1H2H_1\Rightarrow H_2 denote the tournament formed from disjoint copies by orienting every arc from H1H_1 to H2H_2, and let Δ(H1,H2,H3)\Delta(H_1,H_2,H_3) denote the cyclic composition of three tournaments. Write kk for the transitive tournament TTkTT_k. For every kk, define

Hk=TTk(Δ(k,1,1)TTk),H_k=TT_k\Rightarrow(\Delta(k,1,1)\Rightarrow TT_k),

and let AH\mathcal{AH} be the class of tournaments that occur as subtournaments of some HkH_k.

The acyclic hero conjecture. A tournament HH is an acyclic hero if and only if HAHH\in\mathcal{AH}.

The forward implication is proved in the paper, as are several examples of tournaments in AH\mathcal{AH} 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

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.