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 |