# Journal of Combinatorics

## Volume 7 (2016)

### Number 2–3

Guest editors: Rong Luo and Cun-Quan Zhang

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

Pages: 481 – 493

DOI: http://dx.doi.org/10.4310/JOC.2016.v7.n2.a13

#### Authors

Yanbo Zhang (Faculty of EEMCS, University of Twente, Enschede, The Netherlands; and Department of Mathematics, Nanjing University, Nanjing, China)

Hajo Broersma (Faculty of EEMCS, University of Twente, Enschede, The Netherlands)

Yaojun Chen (Department of Mathematics, Nanjing University, Nanjing, China)

#### Abstract

Given two graphs $G_1$ and $G_2$, the Ramsey number $R(G_1, G_2)$ is the smallest integer $N$ such that, for any graph $G$ of order $N$, either $G_1$ is a subgraph of $G$, or $G_2$ is a subgraph of the complement of $G$. Let $C_m$ denote a cycle of order $m$, $K_{1,n}$ a star of order $n+1$ and $W_n$ a wheel of order $n+1$. Already back in the 1970s, exact values of the Ramsey numbers $R(C_m,K_{1,n})$ have been determined for all $m\geq2n$ and for all odd $m\leq2n-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(C_m,K_{1,n})=2n$ for even $m$ with $n<m< 2n$, and that $R(C_m,K_{1,n})=2m-1$ for even $m$ with $3n/4+1\leq m\leq n$. In addition, we determine another six formerly unknown exact values of Ramsey numbers, namely $R(C_6,K_{1,n})$ for $7\leq n\leq11$, and $R(C_6,W_9)$.

#### Keywords

Ramsey number, cycle, star

#### 2010 Mathematics Subject Classification

Primary 05C55. Secondary 05D10.

Full Text (PDF format)

Published 23 February 2016