Antidirected subgraphs of oriented graphs

arXiv2212.00769MaRDI QIDQ6507204FDOQ6507204

Camila Zárate-Guerén, Maya Stein

Abstract: We show that for every $eta>0$ every sufficiently large $n$-vertex oriented graph D of minimum semidegree exceeding $(1+eta)k/2$ contains every balanced antidirected tree with $k$ edges and bounded maximum degree, if $kgeetan$. In particular, this asymptotically confirms a conjecture of the first author for long antidirected paths. Further, we show that in the same setting, D contains every $k$-edge antidirected subdivision of a sufficiently small complete graph, if the paths of the subdivision that have length 1 or 2 span a forest. As a special case, we can find all antidirected cycles of length at most k. Finally, we address a conjecture of Addario-Berry, Havet, Linhares Sales, Reed and Thomass'e for antidirected trees in digraphs. We show that this conjecture is asymptotically true in $n$-vertex oriented graphs for all balanced antidirected trees of bounded maximum degree and of size linear in $n$.

This page was built for publication: Antidirected subgraphs of oriented graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6507204)