Some Upper Bounds on Ramsey Numbers Involving $C_4$

Abstract

We obtain some new upper bounds on the Ramsey numbers of the form $R(\underset{m}{\underbrace{C_4,\dots ,C_4}},G_1,\dots ,G_n)$, where $m\ge 1$ and $G_1,\dots ,G_n$ are arbitrary graphs. We focus on the cases of $G_i$'s being complete, star $K_{1,k}$ or book graphs $B_k$, where $B_k=K_2+k{K}_1$. If $k\ge 2$, then our main upper bound theorem implies that $$R(C_4,B_k)\le R(C_4,K_{1,k})+\lceil \sqrt{R(C_4,K_{1,k})}\rceil +1.$$ Our techniques are used to obtain new upper bounds in several concrete cases, including: $R(C_4,K_{11})\le 43$, $R(C_4,K_{12})\le 51$, $R(C_4,K_3,K_4)\le 29$, $R(C_4,K_4,K_4)\le 66$, $R(C_4,K_3,K_3,K_3)\le 57$, $R(C_4,C_4,K_3,K_4)\le 75$, and $R(C_4,C_4,K_4,K_4)\le 177$, and also $R(C_4,B_{17})\le 28$.

12 pages