`a`
Electronic Research Announcements in Mathematical Sciences (ERA-MS)
 

The approximate Loebl-Komlós-Sós conjecture and embedding trees in sparse graphs
Pages: 1 - 11, January 2015

doi:10.3934/era.2015.22.1      Abstract        References        Full text (423.3K)                  Related Articles

Jan Hladký - Institute of Mathematics, Czech Academy of Science, Žitná 25, 110 00, Praha, Czech Republic (email)
Diana Piguet - Institute of Computer Science, Czech Academy of Sciences, Pod Vodárenskou vĕží 2, 182 07 Prague, Czech Republic (email)
Miklós Simonovits - Rényi Institute, Budapest, Hungary (email)
Maya Stein - Centro de Modelamiento Matemático, Universidad de Chile, Beauchef 851, Santiago Centro, RM, Chile (email)
Endre Szemerédi - Department of Mathematics, Rutgers University, 110 Frelinghuysen Rd., Piscataway, NJ 08854-8019, United States (email)

1 M. Ajtai, J. Komlós and E. Szemerédi, On a conjecture of Loebl, in Graph Theory, Combinatorics, and Algorithms, Vol. 1, 2 (Kalamazoo, MI, 1992), Wiley-Intersci. Publ., Wiley, New York, 1995, 1135-1146.       
2 M. Ajtai, J. Komlós, M. Simonovits and E. Szemerédi, Proof of the Erdős-T. Sós conjecture for large trees, in preparation.
3 N. Alon, A. Shapira and U. Stav, Can a graph have distinct regular partitions?, SIAM J. Discrete Math., 23 (2008/09), 278-287.       
4 C. Borgs, J. Chayes and L. Lovász, Moments of two-variable functions and the uniqueness of graph limits, Geom. Func. Anal., 19 (2010), 1597-1619.       
5 S. Brandt and E. Dobson, The Erdős-Sós conjecture for graphs of girth $5$, Discr. Math., 150 (1996), 411-414.       
6 C. Bazgan, H. Li and M. Woźniak, On the Loebl-Komlós-Sós conjecture, J. Graph Theory, 34 (2000), 269-276.       
7 O. Cooley, Proof of the Loebl-Komlós-Sós conjecture for large, dense graphs, Discrete Math., 309 (2009), 6190-6228.       
8 E. Dobson, Constructing trees in graphs whose complement has no $K_{2,s}$, Combin. Probab. Comput., 11 (2002), 343-347.       
9 P. Erdős, Z. Füredi, M. Loebl and V. T. Sós, Discrepancy of trees, Studia Sci. Math. Hungar., 30 (1995), 47-57.       
10 P. Erdős and T. Gallai, On maximal paths and circuits of graphs, Acta Math. Acad. Sci. Hungar, 10 (1959), 337-356 (unbound insert).       
11 Z. Füredi and M. Simonovits, The history of degenerate (bipartite) extremal graph problems, in Erdös Centennial, Bolyai Soc. Math. Stud., 25, János Bolyai Math. Soc., Budapest, 2013, 169-264.       
12 L. Gerencsér and A. Gyárfás, On Ramsey-type problems, Ann. Univ. Sci. Budapest. Eötvös Sect. Math., 10 (1967), 167-170.       
13 P. E. Haxell, Tree embeddings, J. Graph Theory, 36 (2001), 121-130.       
14 J. Hladký, J. Komlós, D. Piguet, M. Simonovits, M. Stein and E. Szemerédi, The approximate Loebl-Komlós-Sós conjecture, arXiv:1211.3050.
15 J. Hladký, J. Komlós, D. Piguet, M. Simonovits, M. Stein and E. Szemerédi, The approximate Loebl-Komlós-Sós conjecture I: The sparse decomposition, arXiv:1408.3858.
16 J. Hladký, J. Komlós, D. Piguet, M. Simonovits, M. Stein and E. Szemerédi, The approximate Loebl-Komlós-Sós conjecture II: The rough structure of LKS graphs, arXiv:1408.3871.
17 J. Hladký, J. Komlós, D. Piguet, M. Simonovits, M. Stein and E. Szemerédi, The approximate Loebl-Komlós-Sós conjecture III: The finer structure of LKS graphs, arXiv:1408.3866.
18 J. Hladký, J. Komlós, D. Piguet, M. Simonovits, M. Stein and E. Szemerédi, The approximate Loebl-Komlós-Sós conjecture IV: Embedding techniques and the proof of the main result, arXiv:1408.3870.
19 P. E. Haxell, T. Luczak and P. W. Tingley, Ramsey numbers for trees of small maximum degree, Combinatorica, 22 (2002), 287-320.       
20 J. Hladký and D. Piguet, Loebl-Komlós-Sós Conjecture: Dense case, arXiv:0805.4834.
21 D. Kühn and D. Osthus, Embedding large subgraphs into dense graphs, in Surveys in Combinatorics 2009, London Math. Soc. Lecture Note Ser., 365, Cambridge Univ. Press, Cambridge, 2009, 137-167.       
22 J. Komlós, G. Sárközy and E. Szemerédi, Proof of the Seymour conjecture for large graphs, Ann. Comb., 2 (1998), 43-60.       
23 J. Komlós, G. N. Sárközy and E. Szemerédi, Proof of the Seymour conjecture for large graphs, Ann. Comb., 2 (1998), 43-60.
24 J. Komlós, A. Shokoufandeh, M. Simonovits and E. Szemerédi, The regularity lemma and its applications in graph theory, in Theoretical Aspects of Computer Science (Tehran, 2000), Lecture Notes in Comput. Sci., 2292, Springer, Berlin, 2002, 84-112.       
25 I. Levitt, G. N. Sárközy and E. Szemerédi, How to avoid using the regularity lemma: Pósa's conjecture revisited, Discrete Math., 310 (2010), 630-641.       
26 D. Piguet and M. J. Stein, The Loebl-Komlós-Sós conjecture for trees of diameter 5 and for certain caterpillars, Electron. J. Combin., 15 (2008), Research Paper 106, 11 pp.       
27 D. Piguet and M. J. Stein, An approximate version of the Loebl-Komlós-Sós conjecture, J. Combin. Theory Ser. B, 102 (2012), 102-125.       
28 S. N. Soffer, The Komlós-Sós conjecture for graphs of girth 7, Discrete Math., 214 (2000), 279-283.       
29 J.-F. Saclé and M. Woźniak, The Erdős-Sós conjecture for graphs without $C_4$, J. Combin. Theory (Series B), 70 (1997), 367-372.       
30 E. Szemerédi, Regular partitions of graphs, in Problèmes Combinatoires et Théorie des Graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976), Colloq. Internat. CNRS, 260, CNRS, Paris, 1978, 399-401.       
31 M. Woźniak, On the Erdős-Sós conjecture, J. Graph Theory, 21 (1996), 229-234.       
32 Y. Zhao, Proof of the $(n/2-n/2-n/2)$ conjecture for large $n$, Electron. J. Combin., 18 (2011), Paper 27, 61 pp.       

Go to top