The heroic forbidden-set conjecture for oriented forests and heroes

About 5 years old · traced to

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.

References

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.