RANDOM GRAPHS WITH MONOCHROMATIC TRIANGLES IN EVERY EDGE-COLORING

Authors
RODL V RUCINSKI A
Citation
V. Rodl et A. Rucinski, RANDOM GRAPHS WITH MONOCHROMATIC TRIANGLES IN EVERY EDGE-COLORING, Random structures & algorithms, 5(2), 1994, pp. 253-270
Citations number
9
Categorie Soggetti
Mathematics,Mathematics,Mathematics,"Computer Science Software Graphycs Programming
Journal title
Random structures & algorithms → ACNP
ISSN journal
10429832
Volume
5
Issue
2
Year of publication
1994
Pages
253 - 270
Database
ISI
SICI code
1042-9832(1994)5:2<253:RGWMTI>2.0.ZU;2-F
Abstract
We prove that for every r greater-than-or-equal-to 2 there is C > 0 su ch that if p > Cn-1/2 then almost surely every r-coloring of the edges of the binomial random graph K(n, p) results in a monochromatic trian gle. (C) 1994 John Wiley & Sons, Inc.