### Abstract

For every 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. If d ∈ (2k log k - log k, 2k log k) we further prove that the chromatic number almost surely equals k + 1.

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

Title of host publication | Conference Proceedings of the Annual ACM Symposium on Theory of Computing |

Pages | 587-593 |

Number of pages | 7 |

State | Published - 2004 |

Event | Proceedings of the 36th Annual ACM Symposium on Theory of Computing - Chicago, IL, United States Duration: Jun 13 2004 → Jun 15 2004 |

### Other

Other | Proceedings of the 36th Annual ACM Symposium on Theory of Computing |
---|---|

Country | United States |

City | Chicago, IL |

Period | 6/13/04 → 6/15/04 |

### Keywords

- Chromatic Number
- Graph Coloring
- Random Graphs

### ASJC Scopus subject areas

- Software

## Cite this

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

*Conference Proceedings of the Annual ACM Symposium on Theory of Computing*(pp. 587-593)