THE CHROMATIC NUMBER OF RANDOM GRAPHS

被引：127

作者：

LUCZAK, T

机构：

[1] UNIV MINNESOTA,INST MATH & APPLICAT,MINNEAPOLIS,MN 55455

[2] ADAM MICKIEWICZ UNIV,INST MATH,PL-61712 POZNAN,POLAND

来源：

COMBINATORICA | 1991年 / 11卷 / 01期

关键词：

AMS subject classification (1991): 05C80; 05C15;

D O I：

10.1007/BF01375472

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Let chi(G(n,p)) denote the chromatic number of the random graph G(n,p). We prove that there exists a constant d0 such that for np(n) > d0, p(n) --> 0, the probability that [GRAPHICS] tends to 1 as n --> infinity.

引用

页码：45 / 54

页数：10