Vertex Ramsey properties of randomly perturbed graphs

Abstract

Given graphs F, H and G, we say that G is (F, H)(v)-Ramsey if every red/blue vertex coloring of G contains a red copy of F or a blue copy of H. Results of Luczak, Rucinski and Voigt, and Kreuter determine the threshold for the property that the random graph G(n, p) is (F, H)(v)-Ramsey. In this paper we consider the sister problem in the setting ofrandomly perturbed graphs. In particular, we determine how many random edges one needs to add to a dense graph to ensure that with high probability the resulting graph is (F, H)(v)-Ramsey for all pairs (F, H) that involve at least one clique.