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

Abstract

A graph $G$ is called $H$-good if $R(G,H)=(|G|-1)(\chi (H)-1)+\sigma (H)$, where $\sigma (H)$ denotes the size of the smallest color class in a $\chi (H)$-coloring of $H$. In Ramsey theory, it is an interesting problem to study whether a graph $G$ is $H$-good or not. In this article, we study the Ramsey goodness of the pair $(K_{2,n},C_m)$, which naturally lies between the classical star-cycle and book-cycle problems. We prove that \begin{equation*} R(K_{2,n},C_{\{m,m+1\}})=m+1. \end{equation*} for all $m\ge 2n+1$, and consequently establish that \begin{equation*} R(K_{2,n},C_{m})=m+1. \end{equation*} for all $m\ge 3n+4$. This proves that $C_m$ is $K_{2,n}$-good in this range and improves a particular case of a result on the Ramsey goodness by Pokrovskiy and Sudakov. Further, we provide a construction of a graph that disproves the $C_m$-goodness of $K_{2,n}$ for all even $m$ satisfying $n\ge m+2$.

16 pages, 3 figures