Lower bounds for r2(K1+G)r2(K1+G) and r3(K1+G)r3(K1+G) from Paley graph and generalization

Let q≡1(mod4) be a prime power and PqPq the Paley graph of order qq. It is shown that if PqPq contains no copy of GG, where δ(G)≥1δ(G)≥1, then r2(K1+G)≥2q+1r2(K1+G)≥2q+1. In particular, if 4n+14n+1 is a prime power, then r2(K3+K¯n)≥8n+3. Furthermore, the Paley graph PqPq for q=1(mod6) is generalized to H0(q)H0(q), H1(q)H1(q) and H2(q)H2(q), which are (q−1)/3(q−1)/3-regular, isomorphic to each other and form an edge-coloring of KqKq. It is shown that if H0(q)H0(q) contains no copy of GG with δ(G)≥1δ(G)≥1, then r3(K1+G)≥3q+1r3(K1+G)≥3q+1. Also, each pair of adjacent vertices in H0(q)H0(q) has the same number of common neighbors. We shall compute this number for many H0(p)H0(p), where pp is a prime for convenience of the algorithm. Each of computing data gives lower bounds for some three-color Ramsey numbers.