The Ramsey Numbers $R(K_3,K_8–e)$ and $R(K_3,K_9–e)$

Abstract

We give a general construction of a triangle-free graph on $4p$ points whose complement does not contain $K_{p+2}–e$ for $p\ge 4$. This implies that the Ramsey number $R(K_3,K_k–e)\ge 4k–7$ for $k\ge 6$. We also present a cyclic triangle-free graph on $30$ points whose complement does not contain $K_9–e$. The first construction gives lower bounds equal to the exact values of the corresponding Ramsey numbers for $k=6,7,$ and $8$. The upper bounds are obtained by using computer algorithms. In particular, we obtain two new values of Ramsey numbers $R(K_3,K_8–e)=25$ and $R(K_3,K_9–e)=31$, the bounds $36\le R(K_3,K_{10}–e)\le 39$, and the uniqueness of extremal graphs for Ramsey numbers $R(K_3,K_6–e)$ and $R(K_3,K_7–e)$.