The Ramsey number \(R(3,K_{10}-e)\) and computational bounds for \(R(3,G)\) (Q396940)

Summary: Using computer algorithms we establish that the Ramsey number \(R(3,K_{10}-e)\) is equal to 37, which solves the smallest open case for Ramsey numbers of this type. We also obtain new upper bounds for the cases of \(R(3,K_k-e)\) for \(11 \leq k \leq 16\), and show by construction a new lower bound \(55 \leq R(3,K_{13}-e)\). The new upper bounds on \(R(3,K_k-e)\) are obtained by using the values and lower bounds on \(e(3,K_l-e,n)\) for \(l \leq k\), where \(e(3,K_k-e,n)\) is the minimum number of edges in any triangle-free graph on \(n\) vertices without \(K_k-e\) in the complement. We complete the computation of the exact values of \(e(3,K_k-e,n)\) for all \(n\) with \(k \leq 10\) and for \(n \leq 34\) with \(k = 11\), and establish many new lower bounds on \(e(3,K_k-e,n)\) for higher values of \(k\). Using the maximum triangle-free graph generation method, we determine two other previously unknown Ramsey numbers, namely \(R(3,K_{10}-K_3-e)=31\) and \(R(3,K_{10}-P_3-e)=31\). For graphs \(G\) on 10 vertices, besides \(G=K_{10}\), this leaves 6 open cases of the form \(R(3,G)\). The hardest among them appears to be \(G=K_{10}-2K_2\), for which we establish the bounds \(31 \leq R(3,K_{10}-2K_2) \leq 33\).