Hostname: page-component-8448b6f56d-wq2xx Total loading time: 0 Render date: 2024-04-18T17:45:42.567Z 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.
Get access Rights & Permissions [Opens in a new window]

Abstract

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
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 23 , Issue 4 , July 2014 , pp. 607 - 630
Copyright
Copyright © Cambridge University Press 2014 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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