Unavoidable subgraphs in digraphs with large out-degrees

Source abstract

Abstract. We ask the question, Which oriented trees [Formula: see text] 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 [Formula: see text] of in-degree at least 2 must be on the same “level” in the natural height function of [Formula: see text]. 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 [Formula: see text] and [Formula: see text], respectively, contains the [Formula: see text]-subdivision of the in-star with [Formula: see text] leaves as a subgraph; this would be tight and generalizes a conjecture of Thomassé. We prove this for digraphs and [Formula: see text] up to a factor of less than 2.