The two possible values of the chromatic number of a random graph
Preprint
Abstract
Given d \in (0,infty) let k_d be the smallest integer k such that d < 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.Keywords
All Related Versions
This publication has 7 references indexed in Scilit:
- Sharp thresholds of graph properties, and the $k$-sat problemJournal of the American Mathematical Society, 1999
- The concentration of the chromatic number of random graphsCombinatorica, 1997
- The chromatic number of random graphsCombinatorica, 1991
- The chromatic number of random graphsCombinatorica, 1988
- A geometric inequality with applications to linear formsPacific Journal of Mathematics, 1979
- Cliques in random graphsMathematical Proceedings of the Cambridge Philosophical Society, 1976
- On colouring random graphsMathematical Proceedings of the Cambridge Philosophical Society, 1975