A Computational Approach for the Ramsey Numbers R(C_4, K_n)
Stanisław Radziszowski, Kung-Kuen Tse · RIT Scholar Works (Rochester Institute of Technology) · 2002
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 < = R(C_4,K_7) < = 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_7)-graphs on at least 19 vertices. Most of the results are based on computer algorithms.