Premium
On the chromatic number of random graphs
Author(s) -
McDiarmid Colin
Publication year - 1990
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.3240010404
Subject(s) - random graph , combinatorics , mathematics , chromatic scale , binary logarithm , discrete mathematics , random regular graph , brooks' theorem , enhanced data rates for gsm evolution , graph , chordal graph , 1 planar graph , computer science , telecommunications
We consider random graphs G n,p with fixed edge‐probability p. We refine an argument of Bollobás to show that almost all such graphs have chromatic number equal to n /{2 log b n − 2 log b log b n + O (1)} where b = 1/(1 − p ).