2025/04/29 by Tomáš Hons, Tereza Klimošová, Hons, Tomáš +9 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.2504.20616
openalex publication_date 2025/04/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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ℓ and kℓ/2, respectively, contains the (k-1)-subdivision of the in-star with ℓ 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.