On heroes in digraphs with forbidden induced forests

Carbonero A, Koerts H, Moore B, Spirkl S. 2024. On heroes in digraphs with forbidden induced forests. European Journal of Combinatorics. 125, 104104.


Journal Article | Epub ahead of print | English

Scopus indexed
Author
Carbonero, Alvaro; Koerts, Hidde; Moore, BenjaminISTA; Spirkl, Sophie

Corresponding author has ISTA affiliation

Department
Abstract
We continue a line of research which studies which hereditary families of digraphs have bounded dichromatic number. For a class of digraphs C, a hero in C is any digraph H such that H -free digraphs in C have bounded dichromatic number. We show that if F is an oriented star of degree at least five, the only heroes for the class of F -free digraphs are transitive tournaments. For oriented stars F of degree exactly four, we show the only heroes in F -free digraphs are transitive tournaments, or possibly special joins of transitive tournaments. Aboulker et al. characterized the set of heroes of {H,K1+P2→} -free digraphs almost completely, and we show the same characterization for the class of {H,rK1+P3→} -free digraphs. Lastly, we show that if we forbid two "valid" orientations of brooms, then every transitive tournament is a hero for this class of digraphs.
Publishing Year
Date Published
2024-12-26
Journal Title
European Journal of Combinatorics
Publisher
Elsevier
Acknowledgement
We thank the anonymous referees for their careful proofreading which helped improve the presentation of this paper. We also thank one of the anonymous referees for pointing out our construction implies Theorem 1.7!
Volume
125
Article Number
104104
ISSN
IST-REx-ID

Cite this

Carbonero A, Koerts H, Moore B, Spirkl S. On heroes in digraphs with forbidden induced forests. European Journal of Combinatorics. 2024;125. doi:10.1016/j.ejc.2024.104104
Carbonero, A., Koerts, H., Moore, B., & Spirkl, S. (2024). On heroes in digraphs with forbidden induced forests. European Journal of Combinatorics. Elsevier. https://doi.org/10.1016/j.ejc.2024.104104
Carbonero, Alvaro, Hidde Koerts, Benjamin Moore, and Sophie Spirkl. “On Heroes in Digraphs with Forbidden Induced Forests.” European Journal of Combinatorics. Elsevier, 2024. https://doi.org/10.1016/j.ejc.2024.104104.
A. Carbonero, H. Koerts, B. Moore, and S. Spirkl, “On heroes in digraphs with forbidden induced forests,” European Journal of Combinatorics, vol. 125. Elsevier, 2024.
Carbonero A, Koerts H, Moore B, Spirkl S. 2024. On heroes in digraphs with forbidden induced forests. European Journal of Combinatorics. 125, 104104.
Carbonero, Alvaro, et al. “On Heroes in Digraphs with Forbidden Induced Forests.” European Journal of Combinatorics, vol. 125, 104104, Elsevier, 2024, doi:10.1016/j.ejc.2024.104104.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data ISTA Research Explorer

Sources

arXiv 2306.04710

Search this title in

Google Scholar