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

Jan Goedgebeur¹ ; Stanisław P. Radziszowski²

¹Department of Applied Mathematics and Computer Science Ghent University, B-9000 Ghent, Belgium
²Department of Computer Science Rochester Institute of Technology Rochester, NY 14623, USA

The electronic journal of combinatorics, Tome 20 (2013) no. 4

Résumé

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 \le k \le 16$, and show by construction a new lower bound $55 \le 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 \le 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 \le R(3,K_{10}-2K_2) \le 33$.

Détail

DOI : 10.37236/3684

Classification : 05C55, 05C30, 68R10
Mots-clés : Ramsey number, triangle-free graphs, almost-complete graphs, computation