Ramsey Numbers for Triangles versus Almost-Complete Graphs

Abstract

We show that, in any coloring of the edges of $K_{36}$, with two colors, there exists a triangle in the first color or a monochromatic $K_{10}-e$ ($K_{10}$ with one edge removed) in the second color, and hence we obtain a bound on the corresponding Ramsey number, $R(K_3,K_{10}-e)\le 38$. The new lower bound of $37$ for this number is established by a coloring of $K_{36}$ avoiding triangles in the first color and $K_{10}-e$ in the second color. This improves by one the best previously known lower and upper bounds. We also give the bounds for the next Ramsey number of this type, $42\le R(K_3,K_{11}-e)\le 47$.