Ramsey Numbers for Triangles versus Almost-Complete Graphs

摘要

We show that, in any coloring of the edges of K_(38) 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) ≤ 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 ≤ R(K_3, K_(11) - e) ≤ 47.