A version of the Loebl–Komlós–Sós Conjecture for Skew Trees

0523723 - ÚI 2021 RIV GB eng J - Článek v odborném periodiku
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
Grant CEP: GA ČR GBP202/12/G061; GA ČR GJ16-07822Y
Institucionální podpora: RVO:67985807
Klíčová slova: tree * embedding * extremal graph theory * Loebl-Komlós-Sós conjecture
Obor OECD: Pure mathematics
Impakt faktor: 0.847, rok: 2020
Způsob publikování: Omezený přístup
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.
Trvalý link: http://hdl.handle.net/11104/0308027