Number of the records: 1  

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

  1. 1.
    0504792 - ÚI 2020 RIV US eng J - Journal Article
    Rozhoň, Václav
    A Local Approach to the Erdős-Sós Conjecture.
    SIAM Journal on Discrete Mathematics. Roč. 33, č. 2 (2019), s. 643-664. ISSN 0895-4801. E-ISSN 1095-7146
    R&D Projects: GA ČR GJ16-07822Y
    Institutional support: RVO:67985807
    Keywords : Erdős-Sós conjecture * embedding of trees * extremal combinatorics
    OECD category: Pure mathematics
    Impact factor: 0.750, year: 2019
    Method of publishing: Limited access
    http://dx.doi.org/10.1137/18M118195X

    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.
    Permanent Link: http://hdl.handle.net/11104/0296345

     
    FileDownloadSizeCommentaryVersionAccess
    0504792-aa.pdf9566.3 KBPublisher’s postprintrequire
     
Number of the records: 1