A local approach to the Erdős-Sós conjecture

Abstract

A famous conjecture of Erdős and Sós states that every graph with average degree more than $k-1$ contains all trees with $k$ edges as subgraphs. We prove that the Erdős-Sós conjecture holds approximately, if the size of the embedded tree is linear in the size of the graph, and the maximum degree of the tree is sublinear.

Cited by in corpus (1)

• Maximum and minimum degree conditions for embedding trees