The two possible values of the chromatic number of a random graph

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

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.
17 pages, published version

Keywords

Probability, 60C05

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/130243

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/0706.1725
 http://arxiv.org/abs/0706.1725
 Ann. of Math. (2) 162 (2005), no. 3, 1335--1351

Collections

arXiv