The Ramsey Numbers $R(C_{\le n},K_m)$

Abstract

Let$ex(m,C_{\le n})$ denote the maximum size of a graph of order $m$ and girth at least $n+1$, and $EX(m,C_{\le n})$ be the set of all graphs of girth at least $n+1$ and size $ex(m,C_{\le n})$. The Ramsey number $R(C_{\le n},K_m)$ is the smallest $k$ such that every graph of order $k$ contains either a cycle of order $n$ for some $3\le l\le n$ or a set of $m$ independent vertices. It is known that $ex(2n,C_{\le n})=2n+2$ for $n\ge 4$, and the exact values of $R(C_{\le n},K_m)$ for $n\ge m$ are known. In this paper, we characterize all graphs in $EX(2n,C_{\le n})$ for $n\ge 5$, and then obtain the exact values of $R(C_{\le n},K_m)$ for $m\in \{n,n+1\}$.