Hostname: page-component-74656f9884-8r8nv Total loading time: 0 Render date: 2026-11-09T09:38:25.082Z Has data issue: false hasContentIssue false
  • English
  • Français

Cycles Are Strongly Ramsey-Unsaturated

Published online by Cambridge University Press:  29 April 2014

J. SKOKAN  and
M. STEIN
J. SKOKAN
Affiliation:
Department of Mathematics, London School of Economics and Political Science, Houghton Street, London WC2A 2AE, UK and Department of Mathematics, University of Illinois at Urbana-Champaign, 1409 W. Green Street, Urbana, IL 61801, USA (e-mail: jozef@member.ams.org)
M. STEIN*
Affiliation:
Centro de Modelamiento Matemático, Universidad de Chile, Santiago, Chile (e-mail: mstein@dim.uchile.cl)
*
‡Corresponding author.
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.

We call a graph H Ramsey-unsaturated if there is an edge in the complement of H such that the Ramsey number r(H) of H does not change upon adding it to H. This notion was introduced by Balister, Lehel and Schelp in [J. Graph Theory51 (2006), pp. 22–32], where it is shown that cycles (except for C4) are Ramsey-unsaturated, and conjectured that, moreover, one may add any chord without changing the Ramsey number of the cycle Cn, unless n is even and adding the chord creates an odd cycle.

We prove this conjecture for large cycles by showing a stronger statement. If a graph H is obtained by adding a linear number of chords to a cycle Cn, then r(H)=r(Cn), as long as the maximum degree of H is bounded, H is either bipartite (for even n) or almost bipartite (for odd n), and n is large.

This motivates us to call cycles strongly Ramsey-unsaturated. Our proof uses the regularity method.

Keywords

Primary 05C55Secondary 05D1005C38

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 23 , Issue 4 , July 2014 , pp. 607 - 630
Copyright
Copyright © Cambridge University Press 2014 

References

[1]Allen, P., Brightwell, G. and Skokan, J. (2013) Ramsey-goodness; and otherwise. Combinatorica 33 125–160.Google Scholar
[2]Balister, P., Lehel, J. and Schelp, R. H. (2006) Ramsey unsaturated and saturated graphs. J. Graph Theory 51 22–32.Google Scholar
[3]Benevides, F. (2012) A multipartite Ramsey number for odd cycles. J. Graph Theory 71 293–316.Google Scholar
[4]Bondy, J. A. and Erdős, P. (1973) Ramsey numbers for cycles in graphs. J. Combin. Theory Ser. B 14 46–54.CrossRefGoogle Scholar
[5]Burr, S. A. and Erdős, P. (1975) On the magnitude of generalized Ramsey numbers for graphs. In Infinite and Finite Sets 1, Vol. 10 of Colloquia Mathematica Societatis János Bolyai, North-Holland, pp. 215–240.Google Scholar
[6]Chung, F. R. K. and Graham, R. L. (1975) On multicolor Ramsey numbers for complete bipartite graphs. J. Combin. Theory Ser. B 18 164–169.Google Scholar
[7]Chvatál, V., Rödl, V., Szemerédi, E. and Trotter, W. T. (1983) The Ramsey number of a graph with bounded maximum degree. J. Combin. Theory Ser. B 34 239–243.CrossRefGoogle Scholar
[8]Conlon, D., Fox, J. and Sudakov, B. (2012) On two problems in graph Ramsey theory. Combinatorica 32 513–535.CrossRefGoogle Scholar
[9]Erdős, P. and Gallai, T. (1959) On maximal paths and circuits of graphs. Acta Math. Acad. Sci. Hungar. 10 337–356.Google Scholar
[10]Faudree, R. J. and Schelp, R. H. (1974) All Ramsey numbers for cycles in graphs. Discrete Math. 8 313–329.Google Scholar
[11]Fox, J. and Sudakov, B. (2011) Dependent random choice. Random Struct. Alg. 38 68–99.Google Scholar
[12]Graham, R., Rödl, V., Ruciński, A. (2000) On graphs with linear Ramsey numbers. J. Graph Theory 35 176–192.Google Scholar
[13]Graham, R., Rödl, V., Ruciński, A. (2001) On bipartite graphs with linear Ramsey numbers. Combinatorica 21 199–209.Google Scholar
[14]Kohayakawa, Y., Simonovits, M. and Skokan, J. (2006) Stability of Ramsey numbers for cycles. Manuscript.Google Scholar
[15]Komlós, J. and Simonovits, M. (1996) Szemerédi's regularity lemma and its applications in graph theory. In Combinatorics: Paul Erdős is Eighty, Vol. 2 (Keszthely, 1993), Bolyai Society Mathematical Studies, Springer, pp. 295–352.Google Scholar
[16]Rosta, V. (1973) On a Ramsey type problem of J. A. Bondy and P. Erdős I–II. J. Combin. Theory Ser. B 15 94–120.Google Scholar
[17]Szemerédi, E. (1978) Regular partitions of graphs. In Problèmes Combinatoires et Théorie des Graphes (Orsay 1976), Vol. 260 of Colloques Internationaux du CNRS, CNRS, pp. 399–401.Google Scholar