A Computational Approach for the Ramsey Numbers $R(C_4{K}_n)$

Abstract

For graphs $G$ and $H$, the Ramsey number $R(G,H)$ is the least integer $n$ such that every 2-coloring of the edges of $K_n$ contains a subgraph isomorphic to $G$ in the first color or a subgraph isomorphic to $H$ in the second color. Graph $G$ is a $(C_4,K_n)$-graph if $G$ doesn’t contain a cycle $C_4$ and $G$ has no independent set of order $n$. Jayawardene and Rousseau showed that $21\le R(C_4,K_7)\le 22$. In this work, we determine $R(C_4,K_7)=22$ and $R(C_4,K_8)=26$, and enumerate various families of $(C_4,K_n)$-graphs. In particular, we construct all $(C_4,K_n)$-graphs for $n<7$, and all $(C_4,K_n)$-graphs on at least 19 vertices. Most of the results are based on computer algorithms.