Abstract:

For graphs G and H, the Ramsey number R(G,H) is the least integer n such that every 2coloring 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. 