Aboulker et al.'s conjecture on heroic triples of oriented star forests
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.
Sources & referencesView supporting material
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
Sign in to submit a solution.
No solutions have been posted yet.