Vertex Ramsey properties of randomly perturbed graphs
Vertex Ramsey properties of randomly perturbed graphs
复制标题
随机扰动图的顶点拉姆齐性质
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Andrew Treglown
中科院分区：
文献类型：
--
作者：
Shagnik Das;Patrick Morris;Andrew Treglown
给定图F， H和G，我们说G是（F， H）v‐Ramsey，如果G的每个红/蓝顶点着色都包含F的红色副本或H的蓝色副本，则G是（F， H）v‐Ramsey。Łuczak， Ruciński和Voigt， Kreuter的结果确定了随机图G（n, p）为（F， H）v‐Ramsey的属性的阈值。本文研究了随机摄动图集合中的姊妹问题。特别是，我们确定需要向密集图添加多少随机边，以确保对至少包含一个团的所有对（F， H）的结果图有很高的概率是（F， H） v - Ramsey。
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.
登录
查看更多内容
随机扰动图的拉姆齐性质：派系和循环
DOI：
10.1017/s0963548320000231
发表时间：
2020
期刊：
Combinatorics, Probability and Computing
影响因子：
--
作者：
Das S
通讯作者：
Das S
影响因子：
1
作者：
Böttcher J
通讯作者：
Böttcher J
随机扰动密集图中的平铺
DOI：
10.1017/s0963548318000366
发表时间：
2018
期刊：
Combinatorics, Probability and Computing
影响因子：
--
作者：
BALOGH J
通讯作者：
BALOGH J
随机扰动图中的生成树
影响因子：
1
作者：
F. Joos;J. Kim
通讯作者：
J. Kim