tailieunhanh - Báo cáo toán học: "The Loebl–Koml´s–S´s conjecture for trees of o o diameter 5 and for certain caterpillars"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: The Loebl–Koml´s–S´s conjecture for trees of o o diameter 5 and for certain caterpillars. | The Loebl-Komlós-Sós conjecture for trees of diameter 5 and for certain caterpillars Diana Piguet Maya Jakobine Steiny Submitted Dec 19 2007 Accepted Aug 11 2008 Published Aug 18 2008 Mathematics Subject Classification 05C05 05C35 Abstract Loebl Komlos and Sós conjectured that if at least half the vertices of a graph G have degree at least some k 2 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 T0 of trees T T from the above classes. 1 Introduction Loebl conjectured see 6 that if G is a graph of order n and at least n 2 vertices of G have degree at least n 2 then every tree with at most n 2 edges is a subgraph of G. Komlos and Sós generalised his conjecture to the following. Conjecture 1 Loebl Komlós Sós conjecture 6 . Let k n 2 N and let G be a graph of order n so that at least n 2 vertices of G have degree at least k. Then every tree with at most k edges is a subgraph of G. In Loebl s original form the conjecture has been asymptotically solved by Ajtai Komlos and Szemerodi 1 . Later Zhao 12 has shown the exact version. The authors of this paper prove an asymptotic version of Conjecture 1 for k 2 O n in 10 . The first author together with J. Hladky 9 and independently O. Cooley 4 extended this to the complete dense exact case of the conjecture. The bounds from the conjecture could not be significantly lower. It is easy to see that we need at least one vertex of degree at least k in G. On the other hand the amount of diana@. Institute for Theoretical Computer Science Charles University Malostranské nám. 25 118 00 Praha 1 Czech Republic. Supported by project 1M0545 of Czech Ministry of Education. ymaya@. Instituto de Matemática e Estatistica Universidade de São Paulo Rua do Matão 1010 Sao Paulo SP Brasil. Supported by FAPESP grant no. 05 54051-9. THE ELECTRONIC JOURNAL OF COMBINATORICS .