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 条

[1] The anti-Ramsey threshold of complete graphs
Kohayakawa, Yoshiharu
Mota, Guilherme Oliveira
Parczyk, Olaf
Schnitzer, Jakob
DISCRETE MATHEMATICS, 2023, 346 (05)
[2] Anti-Ramsey Threshold of Cycles for Sparse Graphs
Barros, G. F.
Cavalar, B. P.
Mota, G. O.
Parczyk, O.
ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, 2019, 346 : 89 - 98
[3] On an anti-Ramsey threshold for sparse graphs with one triangle
Kohayakawa, Y.
Konstadinidis, P. B.
Mota, G. O.
JOURNAL OF GRAPH THEORY, 2018, 87 (02) : 176 - 187
[4] Anti-Ramsey threshold of cycles?
Barros, Gabriel Ferreira
Cavalar, Bruno Pasqualotto
Mota, Guilherme Oliveira
Parczyk, Olaf
DISCRETE APPLIED MATHEMATICS, 2022, 323 : 228 - 235
[5] Ramsey simplicity of random graphs
Boyadzhiyska, Simona
Clemens, Dennis
Das, Shagnik
Gupta, Pranshu
COMBINATORICS PROBABILITY AND COMPUTING, 2024,
[6] ON SOME MULTICOLOR RAMSEY PROPERTIES OF RANDOM GRAPHS
Dudek, Andrzej
Pralat, Pawel
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2017, 31 (03) : 2079 - 2092
[7] Asymmetric Ramsey properties of random graphs involving cliques and cycles
Liebenau, Anita
Mattos, Leticia
Mendonca, Walner
Skokan, Jozef
RANDOM STRUCTURES & ALGORITHMS, 2023, 62 (04) : 1035 - 1055
[8] Ramsey goodness of trees in random graphs
Araujo, Pedro
Moreira, Luiz
Pavez-Signe, Matias
RANDOM STRUCTURES & ALGORITHMS, 2023, 62 (04) : 761 - 790
[9] Ramsey numbers of cycles in random graphs
Araujo, Pedro
Pavez-Signe, Matias
Sanhueza-Matamala, Nicolas
RANDOM STRUCTURES & ALGORITHMS, 2024,
[10] Vertex Ramsey properties of randomly perturbed graphs
Das, Shagnik
Morris, Patrick
Treglown, Andrew
RANDOM STRUCTURES & ALGORITHMS, 2020, 57 (04) : 983 - 1006

← 1 2 3 4 5 →