Vertex Ramsey properties of randomly perturbed graphs. Issue 4 (14th October 2020) - Das, Shagnik; Morris, Patrick; Treglown, Andrew
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 Ł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 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.