2025/12/18 by Pokrovskiy, Alexey, Versteegen, Leo, Williams, Ella
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2512.16799
openalex publication_date 2025/12/18 · openalex created_date 2025/12/21 · openalex updated_date 2026/07/28
A variant of the Erdős-Sós conjecture, posed by Havet, Reed, Stein and Wood, states that every graph with minimum degree at least \lfloor 2k/3 \rfloor and maximum degree at least k contains a copy of every tree with k edges. Both degree bounds are best possible. We confirm this conjecture for large trees with bounded maximum degree, by proving that for all Δ∈ ℕ and sufficiently large k∈ ℕ, every graph G with δ(G)≥ \lfloor 2k/3 \rfloor and Δ(G)≥ k contains a copy of every tree T with k edges and Δ(T)≤ Δ. We also prove similar results where alternative degree conditions are considered. For the same class of trees, this verifies exactly a related conjecture of Besomi, Pavez-Signé and Stein, and provides asymptotic confirmations of two others.