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 条
  • [41] Infinite paths and cliques in random graphs
    Berarducci, Alessandro
    Majer, Pietro
    Novaga, Matteo
    [J]. FUNDAMENTA MATHEMATICAE, 2012, 216 (02) : 163 - 191
  • [42] Treewidth of Erdos-Renyi random graphs, random intersection graphs, and scale-free random graphs
    Gao, Yong
    [J]. DISCRETE APPLIED MATHEMATICS, 2012, 160 (4-5) : 566 - 578
  • [43] On large deviation properties of Erdos-Renyi random graphs
    Engel, A
    Monasson, R
    Hartmann, AK
    [J]. JOURNAL OF STATISTICAL PHYSICS, 2004, 117 (3-4) : 387 - 426
  • [44] Ramsey degrees of bipartite graphs:: A primitive recursive proof
    Fouché, WL
    Pretorius, LM
    Swarlepoel, CJ
    [J]. DISCRETE MATHEMATICS, 2005, 293 (1-3) : 111 - 119
  • [45] On the minimum degree of minimal Ramsey graphs for multiple colours
    Fox, Jacob
    Grinshpun, Andrey
    Liebenau, Anita
    Person, Yury
    Szabo, Tibor
    [J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 2016, 120 : 64 - 82
  • [46] Cross over of recurrence networks to random graphs and random geometric graphs
    Jacob, Rinku
    Harikrishnan, K. P.
    Misra, R.
    Ambika, G.
    [J]. PRAMANA-JOURNAL OF PHYSICS, 2017, 88 (02):
  • [47] Cross over of recurrence networks to random graphs and random geometric graphs
    RINKU JACOB
    K P HARIKRISHNAN
    R MISRA
    G AMBIKA
    [J]. Pramana, 2017, 88
  • [48] Random walks on random simple graphs
    Hildebrand, M
    [J]. RANDOM STRUCTURES & ALGORITHMS, 1996, 8 (04) : 301 - 318
  • [49] Upper Bounds on Probability Thresholds for Asymmetric Ramsey Properties
    Kohayakawa, Yoshiharu
    Schacht, Mathias
    Spoehel, Reto
    [J]. RANDOM STRUCTURES & ALGORITHMS, 2014, 44 (01) : 1 - 28
  • [50] Threshold functions for asymmetric Ramsey properties involving cycles
    Kohayakawa, Y
    Kreuter, B
    [J]. RANDOM STRUCTURES & ALGORITHMS, 1997, 11 (03) : 245 - 276
12345