The concentration of the chromatic number of random graphs

被引:54
作者
Alon, N [1 ]
Krivelevich, M [1 ]
机构
[1] Tel Aviv Univ, Raymond & Beverly Sackler Fac Exact Sci, Dept Math, IL-69978 Tel Aviv, Israel
基金
以色列科学基金会;
关键词
05C80; 05C15;
D O I
10.1007/BF01215914
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
We prove that for every constant delta > 0 the chromatic number of the random graph G(n,p) with p = n(-1/2-delta) is asymptotically almost surely concentrated in two consecutive values. This implies that for any beta < 1/2 and any integer valued function r(n) less than or equal to O(n(beta)) there exists a function p(n) such that the chromatic number of G(n,p(n)) is precisely r(n) asymptotically almost surely.
引用
收藏
页码:303 / 313
页数:11
相关论文
共 10 条
[1]  
Alon N., 1993, LONDON MATH SOC LECT, V187, P1
[2]  
Alon N., 1992, PROBABILISTIC METHOD
[3]   THE CHROMATIC NUMBER OF RANDOM GRAPHS [J].
BOLLOBAS, B .
COMBINATORICA, 1988, 8 (01) :49-55
[4]   COVERING THE EDGES OF A RANDOM GRAPH BY CLIQUES [J].
FRIEZE, A ;
REED, B .
COMBINATORICA, 1995, 15 (04) :489-497
[5]  
JENSEN TR, 1995, GRAPH COLOIRNG PROBL
[6]   On the minimal number of edges in color-critical graphs [J].
Krivelevich, M .
COMBINATORICA, 1997, 17 (03) :401-426
[7]   A NOTE ON THE SHARP CONCENTRATION OF THE CHROMATIC NUMBER OF RANDOM GRAPHS [J].
LUCZAK, T .
COMBINATORICA, 1991, 11 (03) :295-297
[8]   THE CHROMATIC NUMBER OF RANDOM GRAPHS [J].
LUCZAK, T .
COMBINATORICA, 1991, 11 (01) :45-54
[9]  
Matula D.W., 1970, P 2 CHAPEL HILL C CO, P356
[10]  
SHAMIR E, 1987, COMBINATORICA, V7, P124