The concentration of the chromatic number of random graphs
type: Item
instance of: scholarly article
title: The concentration of the chromatic number of random graphs
zbMATH Open document ID: 0910.05058
DOI: 10.1007/BF01215914
author: Michael Krivelevich
author: Noga Alon
published in: Combinatorica
publication date: 1999-03-14T00:00:00Z
review text: It is proved that for every \(\delta > 0\) the chromatic number of the random graph \(G(n,p)\) with \(p=n^{-1/2-\delta}\) is asymptotically almost surely concentrated in two consecutive values. This implies that for any \(\beta < 1/2\) and any integer-valued function \(r(n) \leq O(n^{\beta})\) there exists a function \(p(n)\) such that the chromatic number of \(G(n,p(n))\) is equal to \(r(n)\) almost surely.
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 1261132
zbMATH Keywords: random graph
zbMATH Keywords: chromatic number
reviewed by: Jozef Širáň
MaRDI profile type: Publication
cites work: Q3142409
cites work: Q4763387
cites work: The chromatic number of random graphs
cites work: Covering the edges of a random graph by cliques
cites work: On the minimal number of edges in color-critical graphs
cites work: A note on the sharp concentration of the chromatic number of random graphs
cites work: Sharp concentration of the chromatic number on random graphs \(G_{n,p}\)
description: scientific article; zbMATH DE number 1261132