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

Number of the records: 1

1.

SYSNO ASEP	0504792
Document Type	J - Journal Article
R&D Document Type	Journal Article
Subsidiary J	Článek ve WOS
Title	A Local Approach to the Erdős-Sós Conjecture
Author(s)	Rozhoň, Václav (UIVT-O)
Source Title	SIAM Journal on Discrete Mathematics. - : SIAM Society for Industrial and Applied Mathematics - ISSN 0895-4801 Roč. 33, č. 2 (2019), s. 643-664
Number of pages	22 s.
Language	eng - English
Country	US - United States
Keywords	Erdős-Sós conjecture ; embedding of trees ; extremal combinatorics
Subject RIV	BA - General Mathematics
OECD category	Pure mathematics
R&D Projects	GJ16-07822Y GA ČR - Czech Science Foundation (CSF)
Method of publishing	Limited access
Institutional support	UIVT-O - RVO:67985807
UT WOS	000473031300004
EID SCOPUS	85069647119
DOI	10.1137/18M118195X
Annotation	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.
Workplace	Institute of Computer Science
Contact	Tereza Šírová, sirova@cs.cas.cz, Tel.: 266 053 800
Year of Publishing	2020
Electronic address	http://dx.doi.org/10.1137/18M118195X

Number of the records: 1