Embedding trees using minimum and maximum degree conditions

Abstract

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 $\hat{I}”\in \mathbb{N}$ and sufficiently large $k\in \mathbb{N}$, every graph $G$ with $\hat{I}´(G)\ge \lfloor 2k/3\rfloor$ and $\hat{I}”(G)\ge k$ contains a copy of every tree $T$ with $k$ edges and $\hat{I}”(T)\le \hat{I}”$. 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.

44 pages, 4 figures