Open access
Author
Date
2023-06Type
- Journal Article
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 Gyarfas-Sumner conjecture to directed graphs stated by Aboulker et al. Show more
Permanent link
https://doi.org/10.3929/ethz-b-000589552Publication status
publishedExternal links
Journal / series
Journal of Graph TheoryVolume
Pages / Article No.
Publisher
WileySubject
directed graphs; graph coloring; induced subgraphs; Gyárfás–Sumner conjectureOrganisational unit
03672 - Steger, Angelika / Steger, Angelika
More
Show all metadata