
AbstractWe prove a conjecture by Aboulker, Charbit, and Naserasr by showing that every oriented graph in which the out‐neighborhood of every vertex induces a transitive tournament can be partitioned into two acyclic induced subdigraphs. We prove multiple extensions of this result to larger classes of digraphs defined by a finite list of forbidden induced subdigraphs. We thereby resolve several special cases of an extension of the famous Gyárfás–Sumner conjecture to directed graphs stated by Aboulker et al.
500 Naturwissenschaften und Mathematik::510 Mathematik::510 Mathematik, graph coloring, FOS: Mathematics, Mathematics - Combinatorics, directed graphs; graph coloring; induced subgraphs; Gyárfás–Sumner conjecture, induced subgraphs, Combinatorics (math.CO), 05C15, 05C20, Gyárfás–Sumner conjecture, directed graphs
500 Naturwissenschaften und Mathematik::510 Mathematik::510 Mathematik, graph coloring, FOS: Mathematics, Mathematics - Combinatorics, directed graphs; graph coloring; induced subgraphs; Gyárfás–Sumner conjecture, induced subgraphs, Combinatorics (math.CO), 05C15, 05C20, Gyárfás–Sumner conjecture, directed graphs
| citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 6 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
