The Lobel-Komlos-Sos conjecture for trees of diameter 5 and for certain caterpillars
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 |
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 |