Premium
Random graphs with monochromatic triangles in every edge coloring
Author(s) -
Rödl Vojtech,
Ruciński Andrzej
Publication year - 1994
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.3240050202
Subject(s) - monochromatic color , combinatorics , mathematics , random graph , enhanced data rates for gsm evolution , binomial (polynomial) , graph , edge coloring , discrete mathematics , physics , computer science , graph power , line graph , statistics , optics , artificial intelligence
We prove that for every r ⩾ 2 there is C > 0 such 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 triangle. © 1994 John Wiley & Sons, Inc.