Antidirected trees in digraphs
Status partial high confidence
The conjecture remains open in general. The most significant post-2013 advances are: Stein and Trujillo-Negrete (2024) proved the conjecture for all antidirected caterpillars (achieving $|A(D)|>(k-1)|V(D)|$ implies every antidirected $k$-arc caterpillar is present) and for $K_{2,s}$-free digraphs with $s=\lceil k/12\rceil$; Stein and Zárate-Guerén (2022) showed the conjecture is asymptotically true in oriented graphs for all balanced antidirected trees of bounded maximum degree and of size linear in $n$. The full conjecture for arbitrary antidirected trees under pure arc-density conditions is still open.
Cited literature (5)
-
Proves the Addario-Berry et al. conjecture is asymptotically true in $n$-vertex oriented graphs for all balanced antidirected trees of bounded maximum degree and of size linear in $n$, using minimum semidegree $>(1+\eta)(k-1)$ as density surrogate.
-
Conference version presenting asymptotic results for balanced antidirected trees of bounded degree in oriented graphs with high minimum semidegree, addressing the Addario-Berry et al. arc-density conjecture.
-
Comprehensive survey covering all known results on oriented tree containment in digraphs; confirms the Addario-Berry et al. conjecture remains open, with the caterpillar case and diameter-$\leq 3$ case as the main resolved classes.
-
Proves the conjecture fully for antidirected caterpillars (every digraph with $>\!(k-1)n$ arcs contains every antidirected $k$-arc caterpillar), and for $K_{2,\lceil k/12\rceil}$-free digraphs under the same arc-density threshold.
-
Establishes minimum semidegree and maximum degree conditions (replacing arc-density conditions) that guarantee containment of balanced antidirected trees of bounded maximum degree, extending prior asymptotic results.
Reviewer notes. All verified papers use the edge convention 'k arcs in the tree' (i.e., tree order k+1), which is consistent with the OPG formulation after shifting k by 1. The EuroComb 2023 entry (Stein–Zárate-Guerén) may be a conference version of arXiv:2212.00769; if so, only the arXiv paper need be cited. No paper fully resolves the conjecture for all antidirected trees under arc-density conditions. The Klimošová–Stein 2023 result on antidirected paths in oriented graphs was mentioned in the survey but could not be independently verified within the search budget.
Discussion
The value $ k-2 $ would be best possible, since the oriented tree consisting of a vertex dominating $ k-1 $ other vertices is not contained in any digraph in which every vertex has outdegree $ k-2 $ . The condition on the trees be antidirected cannot be suppressed. In a bipartite digraph $ D $ with bipartition $ (A,B) $ such that all arcs are directed from $ A $ to $ B $ , all the trees contained in $ D $ are antidirected. This conjecture for symmetric digraphs is equivalent to the celebrated Erdös-Sos conjecture for undirected graphs. (see [E]). Conjecture Let $ G $ be a graph. If $ |E(G)| > \frac{1}{2} (k-2) |V(G)| $ , then $ G $ contains every tree of order $ k $ . Addario-Berry et al. Conjecture also implies Burr's conjecture (see Oriented trees in n-chromatic digraphs ) for antidirected trees, since every digraph with chromatic number $ 2k-2 $ contains a colour-critical digraph has minimum degree at least $ 2k-3 $ , and so whose number of vertices is at least $ \frac{2k-3}{2}|V(D)| $ , which exceeds $ (k-2) |V(D)| $ . This conjecture has only been proved [AHL+] for antidirected trees of diameter at most $ 3 $ .
Bibliography
-
★
[AHL+]L. Addario-Berry, F. Havet, C. Linhares Sales, B. Reed, and S. Thomassé. Oriented trees in digraphs. Discrete Mathematics, 313(8):967-974, 2013. -
[E]P. Erdös, Some problems in graph theory, Theory of Graphs and Its Applications, M. Fielder, Editor, Academic Press, New York, 1965, pp. 29--36.