Aboulker et al.'s conjecture on heroic triples of oriented star forests

An oriented graph is a digraph with no digons, and its dichromatic number χ(D)\vec{\chi}(D) is the least number of acyclic sets partitioning its vertex set. A digraph is a heroic set obstruction when the class of digraphs excluding every member of the set as an induced subdigraph has bounded dichromatic number; a hero is a tournament with this property when it is the sole nontrivial forbidden tournament. Aboulker et al.'s conjecture. For every orientation of a star forest FF and every hero HH, the oriented graphs excluding FF and HH as induced subdigraphs have bounded dichromatic number. This is the third type in the proposed classification of heroic sets of size three; the source notes that it is known for transitive HH and when FF has at most two vertices, but remains open in general.

Sources & referencesView supporting material

Primary source

Raphael Steiner, “On coloring digraphs with forbidden induced subgraphs”, arXiv:2103.04191 (2021).

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.