On Ramsey number of $K_{2,n}$ versus even cycles

Abstract

For graphs $G$ and $H$, the Ramsey number $R(G,H)$ is the smallest integer $N$ such that every graph $\Gamma$ on $N$ vertices contains $G$ or its complement $\overline{\Gamma }$ contains $H$ as a subgraph. In graph Ramsey theory, the star-cycle Ramsey number is well-studied throughout the years. Whereas the Ramsey number of $K_{2,n}$ versus cycle is challenging to determine due to increased structural complexity. In this article, we have obtained an exact value of the Ramsey number $R(K_{2,n},C_m)$ for even $m\in [n,2n-4008]$ and $n\ge 4516$. In particular, we show that $$R(K_{1,n},C_m)=R(K_{2,n},C_m)$$ for all even $m\in [n,2n-4008]$ and $n\ge 4516$. This leads to an interesting question: For fixed $t$, does there exist $n_0(t)\in \mathbb{N}$ such that $R(K_{1,n},C_m)=R(K_{t,n},C_m)$ for all $n\ge n_0(t)$ and for a given range of even $m$?

17 Pages, 3 Figures