On coloring digraphs with forbidden induced subgraphs
Raphael Steiner · Journal of Graph Theory · 2022
Abstract We 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.