Loading...
Please wait, while we are loading the content...
Similar Documents
Cycles Are Strongly Ramsey-Unsaturated
| Content Provider | Scilit |
|---|---|
| Author | Skokan, J. Stein, M. |
| Copyright Year | 2014 |
| Description | 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 $C_{4}$) are Ramsey-unsaturated, and conjectured that, moreover, one may add any chord without changing the Ramsey number of the cycle $C_{n}$, 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 $C_{n}$, then $r(H)=r(C_{n}$), 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. |
| Related Links | http://arxiv.org/pdf/1203.2259 http://arxiv.org/abs/1203.2259 https://www.cambridge.org/core/services/aop-cambridge-core/content/view/7AD8F7151A9D375A1D249E37FAF500E3/S0963548314000212a.pdf/div-class-title-cycles-are-strongly-ramsey-unsaturated-div.pdf |
| Ending Page | 630 |
| Page Count | 24 |
| Starting Page | 607 |
| ISSN | 09635483 |
| e-ISSN | 14692163 |
| DOI | 10.1017/s0963548314000212 |
| Journal | Combinatorics, Probability and Computing |
| Issue Number | 4 |
| Volume Number | 23 |
| Language | English |
| Publisher | Cambridge University Press (CUP) |
| Publisher Date | 2014-07-01 |
| Access Restriction | Open |
| Subject Keyword | Combinatorics, Probability and Computing Primary 05c55 Secondary 05d10 |
| Content Type | Text |
| Resource Type | Article |
| Subject | Applied Mathematics Statistics and Probability Theoretical Computer Science Computational Theory and Mathematics |
