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 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 and every hero , the oriented graphs excluding and 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 and when has at most two vertices, but remains open in general.
References
Primary source
Raphael Steiner, “On coloring digraphs with forbidden induced subgraphs”, arXiv:2103.04191 (2021).
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
No solutions have been posted yet.