### Abstract

We prove that for every constant δ > 0 the chromatic number of the random graph G(n,p) with p = n^{-1/2-δ} is asymptotically almost surely concentrated in two consecutive values. This implies that for any β < 1/2 and any integer valued function r(n)≤O(n^{β}) there exists a function p(n) such that the chromatic number of G(n,p(n)) is precisely r(n) asymptotically almost surely.

Original language | English (US) |
---|---|

Pages (from-to) | 303-313 |

Number of pages | 11 |

Journal | Combinatorica |

Volume | 17 |

Issue number | 3 |

DOIs | |

State | Published - Jan 1 1997 |

Externally published | Yes |

### All Science Journal Classification (ASJC) codes

- Discrete Mathematics and Combinatorics
- Computational Mathematics

## Fingerprint Dive into the research topics of 'The concentration of the chromatic number of random graphs'. Together they form a unique fingerprint.

## Cite this

Alon, N., & Krivelevich, M. (1997). The concentration of the chromatic number of random graphs.

*Combinatorica*,*17*(3), 303-313. https://doi.org/10.1007/BF01215914