Vertex Ramsey properties of randomly perturbed graphs

Research output: Contribution to journalArticlepeer-review


Colleges, School and Institutes


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.

Bibliographic note

© 2020 The Authors. Random Structures & Algorithms published by Wiley Periodicals LLC. This is an open access article under the terms of the Creative Commons Attribution License, which permits use, distribution and reproduction in any medium, provided the original work is properly cited.


Original languageEnglish
Pages (from-to)983-1006
Number of pages24
JournalRandom Structures and Algorithms
Issue number4
Early online date14 Oct 2020
Publication statusPublished - 1 Dec 2020


  • Ramsey theory, random graphs, randomly perturbed structures