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) \leq 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 \leq R(K_3, K_{11}-e) \leq 47\).