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


Autoria(s): PIGUET, Diana; STEIN, Maya Jakobine
Contribuinte(s)

UNIVERSIDADE DE SÃO PAULO

Data(s)

19/04/2012

19/04/2012

2008

Resumo

Loebl, Komlos, and Sos conjectured that if at least half the vertices of a graph G have degree at least some k is an element of N, 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, T') of trees T, T' from the above classes.

Identificador

ELECTRONIC JOURNAL OF COMBINATORICS, v.15, n.1, 2008

1077-8926

http://producao.usp.br/handle/BDPI/16712

http://www.combinatorics.org/Volume_15/PDF/v15i1r106.pdf

Idioma(s)

eng

Publicador

ELECTRONIC JOURNAL OF COMBINATORICS

Relação

Electronic Journal of Combinatorics

Direitos

openAccess

Copyright ELECTRONIC JOURNAL OF COMBINATORICS

Palavras-Chave #Mathematics, Applied #Mathematics
Tipo

article

original article

publishedVersion