Exact Values and Bounds for Ramsey Numbers of $C_4$ Versus a Star Graph

Abstract

We study Ramsey numbers of the form $R(C_4,K_{1,n})$. We determine the eight previously unknown values of $R(C_4,K_{1,n})$ for $n\le 38$. In particular, we show that $R(C_4,K_{1,27})=33$ and $R(C_4,K_{1,n})=n+7$ for $28\le n\le 33$ and for $n=37$. We also establish new general inequalities relating different values of this function. Specifically, if $m\equiv 2(\mathrm{mod}6)$ with $m\ge 8$, then $R(C_4,K_{1,m^2+3})\le m^2+m+4$, and for all positive integers $a$ and $b$, either $R(C_4,K_{1,a})\ge a+b$ or $R(C_4,K_{1,a+b})\le a+2b$. As consequences, we obtain the functional inequalities $f(2n-f(n)+1)\ge n$ and $f(f(n)+1)\le 2f(n)-n+2$, where $f(n)=R(C_4,K_{1,n})$.

5 pages