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 条
  • [1] A variant of the Erdos-Sos conjecture
    Havet, Frederic
    Reed, Bruce
    Stein, Maya
    Wood, David R.
    JOURNAL OF GRAPH THEORY, 2020, 94 (01) : 131 - 158
  • [2] The Erdos-Sos conjecture for spiders
    Fan, Genghua
    Sun, Lingli
    DISCRETE MATHEMATICS, 2007, 307 (23) : 3055 - 3062
  • [3] The Erdos-Sos conjecture for spiders of large size
    Fan, Genghua
    DISCRETE MATHEMATICS, 2013, 313 (22) : 2513 - 2517
  • [4] The Erdos-Sos conjecture for spiders of four legs
    Fan, Genghua
    Huo, Zhenxiang
    JOURNAL OF COMBINATORICS, 2016, 7 (2-3) : 271 - 283
  • [5] The Erdos-Sos Conjecture for trees of diameter four
    McLennan, A
    JOURNAL OF GRAPH THEORY, 2005, 49 (04) : 291 - 301
  • [6] The Erdos-Sos conjecture for graphs of girth 5
    Brandt, S
    Dobson, E
    DISCRETE MATHEMATICS, 1996, 150 (1-3) : 411 - 414
  • [7] A SPECTRAL ERDOS-SOS THEOREM
    Cioaba, Sebastian
    Desai, Dheer Noal
    Tait, Michael
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2023, 37 (03) : 2228 - 2239
  • [8] On the Erdos-Sos conjecture for graphs having no path with k+4 vertices
    Eaton, Nancy
    Tiner, Gary
    DISCRETE MATHEMATICS, 2013, 313 (16) : 1621 - 1629
  • [9] An Aα-Spectral Erdos-Sos Theorem
    Chen, Ming-Zhu
    Li, Shuchao
    Li, Zhao-Ming
    Yu, Yuantian
    Zhang, Xiao-Dong
    ELECTRONIC JOURNAL OF COMBINATORICS, 2023, 30 (03)
  • [10] On the Erdos- Sos Conjecture for graphs on n = k+4 vertices
    Yuan, Long-Tu
    Zhang, Xiao-Dong
    ARS MATHEMATICA CONTEMPORANEA, 2017, 13 (01) : 49 - 61
1234