The Loebl-Komlos-Sos conjecture for trees of diameter 5 and for certain caterpillars

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

Loebl, Komlos, and Sos conjectured that if at least half the vertices of a graph G have degree at least some k, then every tree with at most k edges is a subgraph of G. We prove the conjecture for all trees of diameter at most 5 and for a class of caterpillars. Our result implies a bound on the Ramsey number r(T,F) of trees T, F from the above classes.
11 pages, 1 figure

Keywords

Combinatorics, 05C05

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/144646

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/0712.3382
 http://arxiv.org/abs/0712.3382

Collections

arXiv