The heroic-set conjecture for oriented forests

From papers

Let HH be a hero and let FF be an oriented forest. An oriented star is an orientation of a star, and a disjoint union of oriented stars is an oriented forest whose connected components are oriented stars. For digraphs D1D_1 and D2D_2, write D1+D2D_1+D_2 for their disjoint union.

Heroic-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 conjecture proposes a characterization for the unresolved case (P2) concerning heroic sets of three digraphs. The paper completely settles the corresponding case involving a complete symmetric digraph and an independent set, while the characterization above addresses sets containing K2\overleftrightarrow K_2, a hero, and an oriented forest.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Pierre Aboulker, Pierre Charbit and Reza Naserasr, “Extension of Gyarfas-Sumner conjecture to digraphs”, arXiv:2009.13319 (2020).

Solutions 0

No solutions have been posted yet.