On heroes in digraphs with forbidden induced forests
Download
Journal Article
| Published
| 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
2025-03-01
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!
Benjamin Moore finished this project while a postdoctoral researcher at Charles University, and was supported by project 22-17398S (Flows and cycles in graphs on surfaces) of the Czech Science Foundation. Benjamin Moore is currently funded by RANDSTRUCT No. 101076777, and appreciates the gracious support. We acknowledge the support of the Natural Sciences and Engineering Research Council of Canada (NSERC), [funding reference number RGPIN-2020-03912]. Cette recherche a été financée par le Conseil de recherches en sciences naturelles et en génie du Canada (CRSNG), [numéro de référence RGPIN-2020-03912]. This project was funded in part by the Government of Ontario .
Volume
125
Article Number
104104
ISSN
IST-REx-ID
All files available under the following license(s):
Creative Commons Attribution 4.0 International Public License (CC-BY 4.0):
Main File(s)
File Name
Access Level

Date Uploaded
2025-04-16
MD5 Checksum
2c75f78f40ebb93d16fe3765bda2905a
Export
Marked PublicationsOpen Data ISTA Research Explorer
Sources
arXiv 2306.04710