The two possible values of the chromatic number of a random graph
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.
@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
Cité par Sources :