### Abstract

Original language | Undefined |
---|---|

Pages (from-to) | 481-493 |

Number of pages | 13 |

Journal | Journal of combinatorics (Somerville) |

Volume | 7 |

Issue number | 2-3 |

DOIs | |

Publication status | Published - Feb 2016 |

### Keywords

- EWI-26877
- MSC-05C
- Cycle
- IR-100080
- Star
- METIS-316849
- Ramsey number

### Cite this

*Journal of combinatorics (Somerville)*,

*7*(2-3), 481-493. https://doi.org/10.4310/JOC.2016.v7.n2.a13

}

*Journal of combinatorics (Somerville)*, vol. 7, no. 2-3, pp. 481-493. https://doi.org/10.4310/JOC.2016.v7.n2.a13

**Narrowing down the gap on cycle-star Ramsey numbers.** / Zhang, Yanbo; Broersma, Haitze J.; Chen, Yaojun.

Research output: Contribution to journal › Article › Academic › peer-review

TY - JOUR

T1 - Narrowing down the gap on cycle-star Ramsey numbers

AU - Zhang, Yanbo

AU - Broersma, Haitze J.

AU - Chen, Yaojun

N1 - eemcs-eprint-26877

PY - 2016/2

Y1 - 2016/2

N2 - Given two graphs G1 and G2, the Ramsey number R(G1,G2) is the smallest integer N such that, for any graph G of order N, either G1 is a subgraph of G, or G2 is a subgraph of the complement of G. Let Cm denote a cycle of order m, K1,n a star of order n + 1 and Wn a wheel of order n + 1. Already back in the 1970s, exact values of the Ramsey numbers R(Cm,K1,n) have been determined for all m ≥ 2n and for all odd m ≤ 2n − 1, but for even m < 2n not many exact values are known. In this paper, we use a result of Bondy on pancyclicity to fill a considerable part of this gap. We show that R(Cm,K1,n) = 2n for even m with n < m < 2n, and that R(Cm,K1,n) = 2m−1 for even m with 3n/4+1 ≤ m ≤ n. In addition, we determine another six formerly unknown exact values of Ramsey numbers, namely R(C6,K1,n) for 7 ≤ n ≤ 11, and R(C6,W9).

AB - Given two graphs G1 and G2, the Ramsey number R(G1,G2) is the smallest integer N such that, for any graph G of order N, either G1 is a subgraph of G, or G2 is a subgraph of the complement of G. Let Cm denote a cycle of order m, K1,n a star of order n + 1 and Wn a wheel of order n + 1. Already back in the 1970s, exact values of the Ramsey numbers R(Cm,K1,n) have been determined for all m ≥ 2n and for all odd m ≤ 2n − 1, but for even m < 2n not many exact values are known. In this paper, we use a result of Bondy on pancyclicity to fill a considerable part of this gap. We show that R(Cm,K1,n) = 2n for even m with n < m < 2n, and that R(Cm,K1,n) = 2m−1 for even m with 3n/4+1 ≤ m ≤ n. In addition, we determine another six formerly unknown exact values of Ramsey numbers, namely R(C6,K1,n) for 7 ≤ n ≤ 11, and R(C6,W9).

KW - EWI-26877

KW - MSC-05C

KW - Cycle

KW - IR-100080

KW - Star

KW - METIS-316849

KW - Ramsey number

U2 - 10.4310/JOC.2016.v7.n2.a13

DO - 10.4310/JOC.2016.v7.n2.a13

M3 - Article

VL - 7

SP - 481

EP - 493

JO - Journal of combinatorics (Somerville)

JF - Journal of combinatorics (Somerville)

SN - 2156-3527

IS - 2-3

ER -