A Local Approach to the Erdős-Sós Conjecture

Authors: Václav Rozhoň
Publication year: 2019
Publication type: Článek v odborném periodiku
Periodical: SIAM Journal on Discrete Mathematics
Projects: Extremal graph theory and applications
Bibliographic citation: ROZHOŇ, Václav. A Local Approach to the Erdős-Sós Conjecture. SIAM Journal on Discrete Mathematics. 2019, 33(2), 643-664. ISSN 0895-4801. E-ISSN 1095-7146
Dostupné z: doi:10.1137/18M118195X.
DOI: 10.1137/18M118195X
ID: 504792
Online record: View online record

Abstract

A famous conjecture of Erdős-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.