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 who also proved that cycles (except for ) are Ramsey-unsaturated, and conjectured that, moreover, one may add any chord without changing the Ramsey number of the cycle , 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 , then , 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.
Recommendations
- Cycle-complete Ramsey numbers
- A cycle or Jahangir Ramsey unsaturated graphs
- Ramsey goodness of cycles
- An anti-Ramsey theorem on cycles
- The Cycle-Complete Graph Ramsey Numbers
- On cycle—Complete graph ramsey numbers
- Ramsey numbers for unions of some cycles
- Anti-Ramsey problems for cycles
- The Ramsey numbers for disjoint unions of cycles
- Ramsey numbers for cycles in graphs
Cites work
- A multipartite Ramsey number for odd cycles
- All Ramsey numbers for cycles in graphs
- Dependent random choice
- On a Ramsey-type problem of J. A. Bondy and P. Erdős. I
- On bipartite graphs with linear Ramsey numbers
- On graphs with linear Ramsey numbers
- On multicolor Ramsey numbers for complete bipartite graphs
- On two problems in graph Ramsey theory
- Ramsey numbers for cycles in graphs
- Ramsey unsaturated and saturated graphs
- Ramsey-goodness -- and otherwise
- The Ramsey number of a graph with bounded maximum degree
Cited in
(3)
This page was built for publication: Cycles Are Strongly Ramsey-Unsaturated
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5495678)
