Star-critical Ramsey numbers for cycles versus the complete graph on 5 vertices

Abstract

Let $G$, $H$ and $K$ represent three graphs without loops or parallel edges and $n$ represent an integer. Given any red blue coloring of the edges of $G$, we say that $K\to (G,H)$, if there exists red copy of $G$ in $K$ or a blue copy of $H$ in $K$. Let $K_n$ represent a complete graph on $n$ vertices, $C_n$ a cycle on $n$ vertices and $S_n=K_{1,n}$ a star on $n+1$ vertices. The Ramsey number $r(G,H)$ is defined as $\min \{n\mid K_n\to (G,H)\}$. Likewise, the star-critical Ramsey number $r_{\ast }(H,G)$ is defined $\min \{k\mid K_{r(G,H)-1}\bigsqcup K_{1,k}\to (H,G)\}$. When $n>3$, in this paper we show that $r_{\ast }(C_n,K_5)=3n-1$ except $r_{\ast }(C_4,K_5)=13$. We also characterize all Ramsey critical $r(C_n,K_5)$ graphs.

23 pages, 15 figures