On coloring digraphs with forbidden induced subgraphs. Issue 2 (21st December 2022)

• Record Type: Journal Article
• Authors: Steiner, Raphael
• Is Part Of: Journal of graph theory. Volume 103:Issue 2(2023)
• Page Start: 323
• Page End: 339
• Publication Date: 2022-12-21
• Subjects: directed graphs -- graph coloring -- Gyárfás–Sumner conjecture -- induced subgraphs; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22920
• Languages: English
• ISSNs: 0364-9024

Abstract

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.