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 colouring of $G$ containsa red copy of $F$ or a blue copy of $H$. Results of Łuczak, Ruciński 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 of \emph{randomly 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.

22 pages, final version