The heroic forbidden-set conjecture for oriented forests and heroes
The heroic forbidden-set conjecture for oriented forests and heroes
Let be a hero, meaning a tournament such that every tournament not containing has bounded dichromatic number, and let 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 is heroic if and only if either is the disjoint union of oriented stars or 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
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.