### Abstract

Given d ∈ (0, ∞) 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.

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

Pages (from-to) | 1335-1351 |

Number of pages | 17 |

Journal | Annals of Mathematics |

Volume | 162 |

Issue number | 3 |

DOIs | |

State | Published - Dec 1 2005 |

### ASJC Scopus subject areas

- Statistics and Probability
- Statistics, Probability and Uncertainty

## Fingerprint Dive into the research topics of 'The two possible values of the chromatic number of a random graph'. Together they form a unique fingerprint.

## Cite this

Achlioptas, D., & Naor, A. (2005). The two possible values of the chromatic number of a random graph.

*Annals of Mathematics*,*162*(3), 1335-1351. https://doi.org/10.4007/annals.2005.162.1335