The Ramsey Numbers \(R( K_3, K_8 — e)\) and \(R( K_3, K_9 — e)\)

We give a general construction of a triangle-free graph on \(4p\) points whose complement does not contain \(K_{p+2} – e\) for \(p \geq 4\). This implies that the Ramsey number \(R(K_3, K_k – e) \geq 4k – 7\) for \(k \geq 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 \leq R(K_3, K_{10} – e) \leq 39\), and the uniqueness of extremal graphs for Ramsey numbers \(R(K_3, K_6 – e)\) and \(R(K_3, K_7 – e)\).