On coloring digraphs with forbidden induced subgraphs
OPEN ACCESS
Loading...
Author / Producer
Date
2023-06
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
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.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
103 (2)
Pages / Article No.
323 - 339
Publisher
Wiley
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
directed graphs; graph coloring; induced subgraphs; Gyárfás–Sumner conjecture
Organisational unit
03672 - Steger, Angelika / Steger, Angelika