A LOCAL APPROACH TO THE ERDOS-SOS CONJECTURE

被引：6

作者：

Rozhon, Vaclav ^{[1
,2
]}

机构：

[1] Charles Univ Prague, Fac Math & Phys, Pod Vodarenskou Vezi 2, Prague 18207, Czech Republic

[2] Czech Acad Sci, Inst Comp Sci, Pod Vodarenskou Vezi 2, Prague 18207, Czech Republic

来源：

SIAM JOURNAL ON DISCRETE MATHEMATICS | 2019年 / 33卷 / 02期

关键词：

Erdos-Sos conjecture; embedding of trees; extremal combinatorics; CONSTRUCTING TREES; GRAPHS;

D O I：

10.1137/18M118195X

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

A famous conjecture of Erdos and Sos states that every graph with average degree more than k - 1 contains all trees with k edges as subgraphs. We prove that the Erdos-Sos 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.

引用

页码：643 / 664

页数：22