We show that if D is an n-vertex digraph with more than $(k-1)n$ arcs that does not contain any of three forbidden digraphs, then D contains every antidirected tree on k arcs. The forbidden digraphs are those orientations of K2, k/12 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 generalises a result for K2, k/12-free graphs by Balasubramanian and Dobson. We also show that every digraph D on n vertices with more than $(k-1)n$ arcs contains every antidirected k-arc caterpillar, thus solving the above conjecture for caterpillars. This generalises a result of Perles.
No takes yet. Share an insight, caveat, or question.
Maya et al. (2024) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: