论文标题
定向图的反向子图
Antidirected subgraphs of oriented graphs
论文作者
论文摘要
我们表明，每$η> 0 $，每个足够大的$ n $ n $ vertex面向最小半透明的图形D超过$（1 +η）k/2 $，包含每个平衡的反向树，具有$ k $ edges and Bounded tem and Bounded最高度，如果$ k \ geηn$。特别是，这种渐近地证实了长期反向路径和密集挖掘的第一作者的猜想。 此外，我们表明，在相同的设置中，D包含一个足够小的完整图的每个$ k $的反向分区，如果长度为1或2的路径跨越了森林。作为特殊情况，我们可以找到最多$ k $的所有反向循环。 最后，我们解决了Addario-berry，Havet，Linhares Sales，Reed和Thomassé的猜想，用于Digraphs中的反向树木。我们证明，对于所有平衡的反向型树，具有界限最大程度和尺寸线性的$ n $ vertex图表中，这种猜想在$ n $ vertex的图中渐近呈正确。
We show that for every $η>0$ every sufficiently large $n$-vertex oriented graph D of minimum semidegree exceeding $(1 + η) k/2$ contains every balanced antidirected tree with $k$ edges and bounded maximum degree, if $k \ge ηn$. In particular, this asymptotically confirms a conjecture of the first author for long antidirected paths and dense digraphs. 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é 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$.
