Hostname: page-component-745bb68f8f-s22k5 Total loading time: 0 Render date: 2025-02-11T18:53:38.548Z Has data issue: false hasContentIssue false
  • English
  • Français

Ramsey Goodness of Bounded Degree Trees

Part of: Graph theory

Published online by Cambridge University Press:  16 January 2018

IGOR BALLA ,
ALEXEY POKROVSKIY  and
BENNY SUDAKOV
IGOR BALLA
Affiliation:
Department of Mathematics, ETH, 8092 Zurich, Switzerland (e-mail: igor.balla@math.ethz.ch, dr.alexey.pokrovskiy@gmail.com, benjamin.sudakov@math.ethz.ch)
ALEXEY POKROVSKIY
Affiliation:
Department of Mathematics, ETH, 8092 Zurich, Switzerland (e-mail: igor.balla@math.ethz.ch, dr.alexey.pokrovskiy@gmail.com, benjamin.sudakov@math.ethz.ch)
BENNY SUDAKOV
Affiliation:
Department of Mathematics, ETH, 8092 Zurich, Switzerland (e-mail: igor.balla@math.ethz.ch, dr.alexey.pokrovskiy@gmail.com, benjamin.sudakov@math.ethz.ch)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Given a pair of graphs G and H, the Ramsey number R(G, H) is the smallest N such that every red–blue colouring of the edges of the complete graph KN contains a red copy of G or a blue copy of H. If a graph G is connected, it is well known and easy to show that R(G, H) ≥ (|G|−1)(χ(H)−1)+σ(H), where χ(H) is the chromatic number of H and σ(H) is the size of the smallest colour class in a χ(H)-colouring of H. A graph G is called H-good if R(G, H) = (|G|−1)(χ(H)−1)+σ(H). The notion of Ramsey goodness was introduced by Burr and Erdős in 1983 and has been extensively studied since then.

In this paper we show that if n≥ Ω(|H| log4 |H|) then every n-vertex bounded degree tree T is H-good. The dependency between n and |H| is tight up to log factors. This substantially improves a result of Erdős, Faudree, Rousseau, and Schelp from 1985, who proved that n-vertex bounded degree trees are H-good when n ≥ Ω(|H|4).

MSC classification

Primary: 05C55: Generalized Ramsey theory
Secondary: 05C05: Trees
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 27 , Issue 3 , May 2018 , pp. 289 - 309
Copyright
Copyright © Cambridge University Press 2018 

References

[1] Allen, P., Brightwell, G. and Skokan, J. (2013) Ramsey-goodness and otherwise. Combinatorica 33 125–160.Google Scholar
[2] Burr, S. (1981) Ramsey numbers involving graphs with long suspended paths. J. London Math. Soc. 24 405–413.Google Scholar
[3] Burr, S. and Erdős, P. (1983) Generalizations of a Ramsey-theoretic result of Chvátal. J. Graph Theory 7 39–51.Google Scholar
[4] Chung, F. R. K.. (1990) Separator theorems and their applications. In Paths, Flows, and VLSILayout, (Korte, B., Lovasz, L., Promel, H. J., and Schriver, A., eds), Springer-Verlag, New York, pp. 17–34.Google Scholar
[5] Chvátal, V. (1977) Tree-complete graph Ramsey number. J. Graph Theory 1 93.CrossRefGoogle Scholar
[6] Conlon, D., Fox, J., Lee, C. and Sudakov, B. (2016) Ramsey numbers of cubes versus cliques. Combinatorica 36 37–70.Google Scholar
[7] Erdős, P. (1947) Some remarks on the theory of graphs. Bull. Amer. Math. Soc. 53 292–294.Google Scholar
[8] Erdős, P., Faudree, R., Rousseau, C. and Schelp, R. (1984) Tree-multipartite graph Ramsey numbers. In Graph Theory and Combinatorics: A Volume in Honor of Paul Erdős (Bollobás, B., ed.), Academic Press, pp. 155–160.Google Scholar
[9] Erdős, P., Faudree, R., Rousseau, C. and Schelp, R. (1985) Multipartite graph-sparse graph Ramsey numbers. Combinatorica 5 311–318.CrossRefGoogle Scholar
[10] Erdős, P., Faudree, R., Rousseau, C. and Schelp, R. (1989) Multipartite graph-tree graph Ramsey numbers. Ann. NY Acad. Sci. 576 146–154.Google Scholar
[11] Erdős, P. and Szekeres, G. (1947) Some remarks on the theory of graphs. Bull. Amer. Math. Soc. 53 292–294.Google Scholar
[12] Fiz Pontiveros, G., Griffiths, S., Morris, R., Saxton, D. and Skokan, J. (2014) The Ramsey number of the clique and the hypercube. J. London Math. Soc. 89 680–702.Google Scholar
[13] Friedman, J. and Pippenger, N. (1987) Expanding graphs contain all small trees. Combinatorica 7 71–76.CrossRefGoogle Scholar
[14] Füredi, Z. and Simonovits, M. (2013) The history of degenerate (bipartite) extremal graph problems. In Erdős Centennial (Lovász, L. e al., eds), Springer, pp. 169–264.Google Scholar
[15] Haxell, P. (2001) Tree embeddings. J. Graph Theory 36 121–130.Google Scholar
[16] Krivelevich, M. (2010) Embedding spanning trees in random graphs. SIAM J. Discrete Math. 24 1495–1500.Google Scholar
[17] Montgomery, R. (2014) Embedding bounded degree spanning trees in random graphs. arXiv:1405.6559Google Scholar
[18] Nikiforov, V. (2005) The cycle-complete graph Ramsey numbers. Combin. Probab. Comput. 14 349–370.CrossRefGoogle Scholar
[19] Nikiforov, V. and Rousseau, C. (2009) Ramsey goodness and beyond. Combinatorica 29 227–262.Google Scholar
[20] Pokrovskiy, A. and Sudakov, B. (2017) Ramsey goodness of paths. J. Combin. Theory Ser. B 122 384–390.Google Scholar
[21] Pokrovskiy, A. and Sudakov, B. Ramsey goodness of cycles. Preprint.Google Scholar
[22] Wilson, R. J. (1996) Introduction to Graph Theory, fourth edition, Longman.Google Scholar