The distribution of the chromatic number on random graphs Gn, p is quite sharply concentrated. For fixed p it concentrates almost surely in √n ω(n) consecutive integers where ω(n) approaches infinity arbitrarily slowly. If the average degree pn is less than n1/6, it concentrates almost surely in five consecutive integers. Large deviation estimates for martingales are used in the proof.
- 05 C 15
- 60 C 05
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
- Computational Mathematics