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: https://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.

Published 23 February 2016