

















We ask the question, which oriented trees $T$ must be contained as subgraphs in every finite directed graph of sufficiently large minimum out-degree. We formulate the following simple condition: all vertices in $T$ of in-degree at least $2$ must be on the same 'level' in the natural height function of $T$. We prove this condition to be necessary and conjecture it to be sufficient. In support of our conjecture, we prove it for a fairly general class of trees. An essential tool in the latter proof, and a question interesting in its own right, is finding large subdivided in-stars in a directed graph of large minimum out-degree. We conjecture that any digraph and oriented graph of minimum out-degree at least $k\ell$ and $k\ell/2$, respectively, contains the $(k-1)$-subdivision of the in-star with $\ell$ leaves as a subgraph; this would be tight and generalizes a conjecture of Thomassé. We prove this for digraphs and $k=2$ up to a factor of less than $2$.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。