On coloring digraphs with forbidden induced subgraphs
dc.contributor.author
Steiner, Raphael
dc.date.accessioned
2023-04-25T15:07:09Z
dc.date.available
2023-01-01T04:53:49Z
dc.date.available
2023-01-04T09:55:35Z
dc.date.available
2023-04-25T15:07:09Z
dc.date.issued
2023-06
dc.identifier.issn
0364-9024
dc.identifier.issn
1097-0118
dc.identifier.other
10.1002/jgt.22920
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/589552
dc.identifier.doi
10.3929/ethz-b-000589552
dc.description.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.
en_US
dc.format
application/pdf
en_US
dc.language.iso
en
en_US
dc.publisher
Wiley
en_US
dc.rights.uri
http://creativecommons.org/licenses/by/4.0/
dc.subject
directed graphs
en_US
dc.subject
graph coloring
en_US
dc.subject
induced subgraphs
en_US
dc.subject
Gyárfás–Sumner conjecture
en_US
dc.title
On coloring digraphs with forbidden induced subgraphs
en_US
dc.type
Journal Article
dc.rights.license
Creative Commons Attribution 4.0 International
dc.date.published
2022-12-21
ethz.journal.title
Journal of Graph Theory
ethz.journal.volume
103
en_US
ethz.journal.issue
2
en_US
ethz.journal.abbreviated
J. graph theory
ethz.pages.start
323
en_US
ethz.pages.end
339
en_US
ethz.version.deposit
publishedVersion
en_US
ethz.identifier.wos
ethz.identifier.scopus
ethz.publication.place
New York, NY
en_US
ethz.publication.status
published
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02643 - Institut für Theoretische Informatik / Inst. Theoretical Computer Science::03672 - Steger, Angelika / Steger, Angelika
en_US
ethz.leitzahl.certified
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02643 - Institut für Theoretische Informatik / Inst. Theoretical Computer Science::03672 - Steger, Angelika / Steger, Angelika
ethz.date.deposited
2023-01-01T04:53:55Z
ethz.source
WOS
ethz.eth
yes
en_US
ethz.availability
Open access
en_US
ethz.rosetta.installDate
2024-02-02T22:07:36Z
ethz.rosetta.lastUpdated
2024-02-02T22:07:36Z
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=On%20coloring%20digraphs%20with%20forbidden%20induced%20subgraphs&rft.jtitle=Journal%20of%20Graph%20Theory&rft.date=2023-06&rft.volume=103&rft.issue=2&rft.spage=323&rft.epage=339&rft.issn=0364-9024&1097-0118&rft.au=Steiner,%20Raphael&rft.genre=article&rft_id=info:doi/10.1002/jgt.22920&
Files in this item
Publication type
-
Journal Article [129217]