Number of the records: 1
A version of the Loebl–Komlós–Sós Conjecture for Skew Trees
- 1.0523723 - ÚI 2021 RIV GB eng J - Journal Article
Klimošová, T. - Piguet, Diana - Rozhoň, Václav
A version of the Loebl–Komlós–Sós Conjecture for Skew Trees.
European Journal of Combinatorics. Roč. 88, August 2020 (2020), č. článku 103106. ISSN 0195-6698. E-ISSN 1095-9971
R&D Projects: GA ČR GBP202/12/G061; GA ČR GJ16-07822Y
Institutional support: RVO:67985807
Keywords : tree * embedding * extremal graph theory * Loebl-Komlós-Sós conjecture
OECD category: Pure mathematics
Impact factor: 0.847, year: 2020
Method of publishing: Limited access
http://dx.doi.org/10.1016/j.ejc.2020.103106
Loebl, Komlós, and Sós conjectured that any graph with at least half of its vertices of degree at least contains every tree with at most edges. We propose a version of this conjecture for skew trees, i.e., we consider the class of trees with at most edges such that the sizes of the colour classes of the trees have a given ratio. We show that our conjecture is asymptotically correct for dense graphs. The proof relies on the regularity method. Our result implies bounds on Ramsey number of several trees of given skew.
Permanent Link: http://hdl.handle.net/11104/0308027
Number of the records: 1