Antidirected Trees in Dense Digraphs
SIAM Journal on Discrete Mathematics · 30.06.2025 · 39 (2) · 698-727
DOI: 10.1137/24m165497x ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Discrete Mathematics, online erschienen am 17.04.2025. Verfasst von Maya Stein und 1 weiteren Autor:innen. Die Arbeit wurde bisher 3-mal zitiert (Crossref) und nennt 14 Literaturangaben. Gefördert von: Fondo Nacional de Desarrollo Científico y Tecnológico, ANID, H2020 Marie Skłodowska-Curie Actions.
Abstract (Originalsprache)
We show that if [Formula: see text] is an [Formula: see text]-vertex digraph with more than [Formula: see text] arcs that does not contain any of three forbidden digraphs, then [Formula: see text] contains every antidirected tree on [Formula: see text] arcs. The forbidden digraphs are those orientations of [Formula: see text] where each of the vertices in the class of size two has either out-degree 0 or in-degree 0. This proves a conjecture of Addario-Berry et al. for a broad class of digraphs, and generalizes a result for [Formula: see text]-free graphs by Balasubramanian and Dobson. We also show that every digraph [Formula: see text] on [Formula: see text] vertices with more than [Formula: see text] arcs contains every antidirected [Formula: see text]-arc caterpillar, thus solving the above conjecture for caterpillars. This generalizes a result of Perles.
Förderung
- Fondo Nacional de Desarrollo Científico y Tecnológico
- ANID
- H2020 Marie Skłodowska-Curie Actions
Zitieren
APA
Stein, M., & Trujillo-Negrete, A. (2025). Antidirected Trees in Dense Digraphs. SIAM Journal on Discrete Mathematics, 39(2), 698-727. https://doi.org/10.1137/24m165497x
Vancouver
Stein M, Trujillo-Negrete A. Antidirected Trees in Dense Digraphs. SIAM Journal on Discrete Mathematics. 2025;39(2):698-727. doi:10.1137/24m165497x
BibTeX
@article{Stein2025,
author = {Stein, Maya and Trujillo-Negrete, Ana},
title = {Antidirected Trees in Dense Digraphs},
journal = {SIAM Journal on Discrete Mathematics},
year = {2025},
volume = {39},
number = {2},
pages = {698--727},
doi = {10.1137/24m165497x}
}
EUVIMED