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 条

[31] A Short Proof of the Random Ramsey Theorem
Nenadov, Rajko
Steger, Angelika
COMBINATORICS PROBABILITY & COMPUTING, 2016, 25 (01) : 130 - 144
[32] Ramsey numbers for multiple copies of sparse graphs
Sulser, Aurelio
Trujic, Milos
JOURNAL OF GRAPH THEORY, 2024, 106 (04) : 843 - 870
[33] DIRECTED GRAPHS WITH LOWER ORIENTATION RAMSEY THRESHOLDS
Barros, Gabriel Ferreira
Cavalar, Bruno Pasqualotto
Kohayakawa, Yoshiharu
Mota, Guilherme Oliveira
Naia, Tassio
RAIRO-OPERATIONS RESEARCH, 2024, 58 (04) : 3607 - 3619
[34] On the Ramsey number of sparse 3-graphs
Nagle, Brendan
Olsen, Sayaka
Roedl, Vojtech
Schacht, Mathias
GRAPHS AND COMBINATORICS, 2008, 24 (03) : 205 - 228
[35] On Anti-stochastic Properties of Unlabeled Graphs
Kiselev, Sergei
Kupavskii, Andrey
Verbitsky, Oleg
Zhukovskii, Maksim
GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE (WG 2022), 2022, 13453 : 300 - 312
[36] On the Ramsey Number of Sparse 3-Graphs
Brendan Nagle
Sayaka Olsen
Vojtěch Rödl
Mathias Schacht
Graphs and Combinatorics, 2008, 24 : 205 - 228
[37] Calculating Ramsey Numbers by Partitioning Colored Graphs
Pokrovskiy, Alexey
JOURNAL OF GRAPH THEORY, 2017, 84 (04) : 477 - 500
[38] RAMSEY THEOREMS FOR KNOTS, LINKS AND SPATIAL GRAPHS
NEGAMI, S
TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 1991, 324 (02) : 527 - 541
[39] RANDOM GRAPHS WITH A RANDOM BIJECTION
Anbo, Yuki
TSUKUBA JOURNAL OF MATHEMATICS, 2011, 35 (01) : 143 - 151
[40] Random triangles in random graphs
Heckel, Annika
RANDOM STRUCTURES & ALGORITHMS, 2021, 59 (04) : 616 - 621

← 1 2 3 4 5 →