Menu
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 \leq R(C_4, K_7) \leq 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.