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
相关论文
共 31 条
1234