Geodesic
The two possible values of the chromatic number of a random graph
Dimitris Achlioptas1 ; Assaf Naor2
1 Microsoft Research, Redmond, WA 98052
2 Princeton University, Princeton, NJ 08544
Annals of mathematics, Tome 162 (2005) no. 3, pp. 1335-1351.

Voir la notice de l'article provenant de la source Annals of Mathematics website

Given $d \in (0,\infty)$ let $k_d$ be the smallest integer $k$ such that $d\lt 2k\log k$. We prove that the chromatic number of a random graph $G(n,d/n)$ is either $k_d$ or $k_d+1$ almost surely.
DOI : 10.4007/annals.2005.162.1335

Dimitris Achlioptas 1 ; Assaf Naor 2

1 Microsoft Research, Redmond, WA 98052
2 Princeton University, Princeton, NJ 08544 
@article{10_4007_annals_2005_162_1335,
     author = {Dimitris Achlioptas and Assaf Naor},
     title = {The two possible values of the chromatic number of a random graph},
     journal = {Annals of mathematics},
     pages = {1335--1351},
     publisher = {mathdoc},
     volume = {162},
     number = {3},
     year = {2005},
     doi = {10.4007/annals.2005.162.1335},
     mrnumber = {2179732},
     zbl = {1094.05048},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.4007/annals.2005.162.1335/}
}
TY  - JOUR
AU  - Dimitris Achlioptas
AU  - Assaf Naor
TI  - The two possible values of the chromatic number of a random graph
JO  - Annals of mathematics
PY  - 2005
SP  - 1335
EP  - 1351
VL  - 162
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.4007/annals.2005.162.1335/
DO  - 10.4007/annals.2005.162.1335
LA  - en
ID  - 10_4007_annals_2005_162_1335
ER  - 
%0 Journal Article
%A Dimitris Achlioptas
%A Assaf Naor
%T The two possible values of the chromatic number of a random graph
%J Annals of mathematics
%D 2005
%P 1335-1351
%V 162
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.4007/annals.2005.162.1335/
%R 10.4007/annals.2005.162.1335
%G en
%F 10_4007_annals_2005_162_1335
Dimitris Achlioptas; Assaf Naor. The two possible values of the chromatic number of a random graph. Annals of mathematics, Tome 162 (2005) no. 3, pp. 1335-1351. doi : 10.4007/annals.2005.162.1335. http://geodesic.mathdoc.fr/articles/10.4007/annals.2005.162.1335/

Cité par Sources :