The heroic forbidden-set conjecture for oriented forests and heroes

Let HH be a hero, meaning a tournament such that every tournament not containing HH has bounded dichromatic number, and let FF be an oriented forest. A set of digraphs is heroic if every digraph with none of its members as an induced subdigraph has bounded dichromatic number. The heroic forbidden-set conjecture. The set {K2,H,F}\{\overleftrightarrow{K_2},H,F\} is heroic if and only if either FF is the disjoint union of oriented stars or HH is a transitive tournament.

This is presented as an analogue of the Gyárfás–Sumner conjecture for oriented graphs. The only-if direction was proved in the cited prior work, while the conjecture is stated to be widely open.

Sources & referencesView supporting material

Primary source

Pierre Aboulker, Guillaume Aubian and Pierre Charbit, “Decomposing and colouring some locally semicomplete digraphs”, arXiv:2103.07886 (2022).

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.