Vertex Ramsey properties of randomly perturbed graphs
Research output: Contribution to journal › Article › peer-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.
© 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.
|Number of pages||24|
|Journal||Random Structures and Algorithms|
|Early online date||14 Oct 2020|
|Publication status||Published - 1 Dec 2020|