Star-critical Ramsey number of $K_4$ versus $F_n$

Abstract

For two graphs $G$ and $H$, the Ramsey number $r(G,H)$ is the smallest positive integer $r$, such that any red/blue coloring of the edges of the graph $K_r$ contains either a red subgraph that is isomorphic to $G$ or a blue subgraph that is isomorphic to $H$. Let $S_k=K_{1,k}$ be a star of order $k+1$ and $K_n\bigsqcup S_k$ be a graph obtained from $K_n$ by adding a new vertex $v$ and joining $v$ to $k$ vertices of $K_n$. The star-critical Ramsey number $r_{\ast }(G,H)$ is the smallest positive integer $k$ such that any red/blue coloring of the edges of graph $K_{r-1}\bigsqcup S_k$ contains either a red subgraph that is isomorphic to $G$ or a blue subgraph that is isomorphic to $H$, where $r=r(G,H)$. In this paper, it is shown that $r_{\ast }(F_n,K_4)=4n+2$, where $n\ge 4$.

arXiv comment11 pages, 3 figures