The chromatic number of random graphs |
| |
Authors: | Tomasz Łuczak |
| |
Affiliation: | 1. Institute for Mathematics and its Applications, University of Minnesota, Minneapolis, USA
|
| |
Abstract: | Let χ(G(n, p)) denote the chromatic number of the random graphG(n, p). We prove that there exists a constantd 0 such that fornp(n)>d 0,p(n)→0, the probability that $$frac{{np}}{{2 log np}}left( {1 + frac{{log log np - 1}}{{log np}}} right)< chi (G(n,p))< frac{{np}}{{2 log np}}left( {1 + frac{{30 log log np}}{{log np}}} right)$$ tends to 1 asn→∞. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|