On the chromatic number of random graphs

被引：23

作者：

Coja-Oghlan, Amin ^{[1
]}

Panagiotou, Konstantinos ^{[2
]}

Steger, Angelika ^{[2
]}

机构：

[1] Carnegie Mellon Univ, Dept Math Sci, Pittsburgh, PA 15213 USA

[2] ETH, Inst Theoret Comp Sci, CH-8092 Zurich, Switzerland

来源：

JOURNAL OF COMBINATORIAL THEORY SERIES B | 2008年 / 98卷 / 05期

关键词：

random graphs; chromatic number;

D O I：

10.1016/j.jctb.2007.11.009

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

In this paper we consider the classical Erdos-Renyi model of random graphs G(n,p). We show that for p = p(n) <= n(-3/4-delta), for any fixed delta > 0, the chromatic number chi(G(n,p)) is a.a.s. l, l + 1, or l + 2, where l is the maximum integer satisfying 2(l - 1) log(l - 1) <= p(n - 1). (C) 2008 Elsevier Inc. All rights reserved.

引用

页码：980 / 993

页数：14

共 11 条

[1] The two possible values of the chromatic number of a random graph [J].

Achlioptas, D ;

Naor, A .

ANNALS OF MATHEMATICS, 2005, 162 (03) :1335-1351

[2]

Achlioptas D, 1999, RANDOM STRUCT ALGOR, V14, P63, DOI 10.1002/(SICI)1098-2418(1999010)14:1<63::AID-RSA3>3.0.CO

[3]

2-7

[4] The concentration of the chromatic number of random graphs [J].

Alon, N ;

Krivelevich, M .

COMBINATORICA, 1997, 17 (03) :303-313

[5]

Alon N., 2004, The probabilistic method

[6] THE CHROMATIC NUMBER OF RANDOM GRAPHS [J].

BOLLOBAS, B .

COMBINATORICA, 1988, 8 (01) :49-55

[7]

Janson S., 2000, WILEY INTERSCI SER D

[8] A NOTE ON THE SHARP CONCENTRATION OF THE CHROMATIC NUMBER OF RANDOM GRAPHS [J].

LUCZAK, T .

COMBINATORICA, 1991, 11 (03) :295-297

[9] THE CHROMATIC NUMBER OF RANDOM GRAPHS [J].

LUCZAK, T .

COMBINATORICA, 1991, 11 (01) :45-54

[10]

os P., 1959, Publ. Math, V6, P290, DOI DOI 10.5486/PMD.1959.6.3-4.12

← 1 2 →