Let Kn-e be a graph obtained from a complete graph of order n by dropping an edge, and let Gp be a Paley graph of order p. It is shown that if Gp contains no Kn-e, then r(Kn+1-e)≥2p+1. For example, G1493 contains no K13-e, so r(K14-e)≥2987, improving the old bound 2557. It is also shown that r(K-bar_2 + G) ≤4r (G, K-bar_2 + G) - 2, implying that r(K_n - e) ≤ 4 r (K_(n-2), K_n-e) - 2.
展开▼
