Anti-Ramsey properties of random graphs

被引：4

作者：

Bohman, Tom ^{[1
]}

Frieze, Alan ^{[1
]}

Pikhurko, Oleg ^{[1
]}

Smyth, Cliff ^{[2
]}

机构：

[1] Carnegie Mellon Univ, Dept Math Sci, Pittsburgh, PA 15213 USA

[2] MIT, Dept Math, Cambridge, MA 02139 USA

来源：

JOURNAL OF COMBINATORIAL THEORY SERIES B | 2010年 / 100卷 / 03期

关键词：

Ramsey theory; Random graphs;

D O I：

10.1016/j.jctb.2009.09.002

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We call a coloring of the edge set of a graph G a b-bounded coloring if no color is used more than b times. We say that a subset of the edges of G is rainbow if each edge is of a different color. A graph has property A(b, H) if every b-bounded coloring of its edges has a rainbow copy of H. We estimate the threshold for the random graph G(n,p) to have property A(b, H). (C) 2009 Elsevier Inc. All rights reserved.

引用

页码：299 / 312

页数：14

共 50 条

[21] Ramsey unsaturated and saturated graphs
Balister, P
Lehel, J
Schelp, RH
JOURNAL OF GRAPH THEORY, 2006, 51 (01) : 22 - 32
[22] ANTI-CONCENTRATION FOR SUBGRAPH COUNTS IN RANDOM GRAPHS
Fox, Jacob
Kwan, Matthew
Sauermann, Lisa
ANNALS OF PROBABILITY, 2021, 49 (03) : 1515 - 1553
[23] On vertex Ramsey graphs with forbidden subgraphs
Diskin, Sahar
Hoshen, Ilay
Krivelevich, Michael
Zhukovskii, Maksim
DISCRETE MATHEMATICS, 2024, 347 (03)
[24] Online Ramsey Theory for Planar Graphs
Petrickova, Sarka
ELECTRONIC JOURNAL OF COMBINATORICS, 2014, 21 (01)
[25] On Ramsey Numbers for Arbitrary Sequences of Graphs
Karas, V. S.
Raigorodskii, A. M.
DOKLADY MATHEMATICS, 2022, 105 (01) : 14 - 17
[26] Ramsey upper density of infinite graphs
Lamaison, Ander
COMBINATORICS PROBABILITY AND COMPUTING, 2023, 32 (05) : 703 - 723
[27] On the Minimum Degree of Minimal Ramsey Graphs
Szabo, Tibor
Zumstein, Philipp
Zuercher, Stefanie
JOURNAL OF GRAPH THEORY, 2010, 64 (02) : 150 - 164
[28] On Ramsey Numbers for Arbitrary Sequences of Graphs
V. S. Karas
A. M. Raigorodskii
Doklady Mathematics, 2022, 105 : 14 - 17
[29] Infinite partitions of random graphs
Vuksanovic, V
JOURNAL OF COMBINATORIAL THEORY SERIES A, 2006, 113 (02) : 225 - 250
[30] ON ISOMORPHISM-INVARIANT ANTISTOCHASTIC PROPERTIES OF RANDOM GRAPHS
Kiselev, Sergei
Kupavskii, Andrey
Verbitsky, Oleg
Zhukovskii, Maksim
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2024, 38 (04) : 3043 - 3078

← 1 2 3 4 5 →