The concentration of the chromatic number of random graphs

Noga Alon; Michael Krivelevich

doi:10.1007/BF01215914

The concentration of the chromatic number of random graphs

Noga Alon, Michael Krivelevich

Research output: Contribution to journal › Article › peer-review

65 Scopus citations

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	https://doi.org/10.1007/BF01215914
State	Published - 1997
Externally published	Yes

All Science Journal Classification (ASJC) codes

Discrete Mathematics and Combinatorics
Computational Mathematics

Access to Document

10.1007/BF01215914

Cite this

@article{19bb361521c649658ea2d79b927591f7,

title = "The concentration of the chromatic number of random graphs",

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.",

author = "Noga Alon and Michael Krivelevich",

note = "Funding Information: Mathematics Subject Classification (1991): 05C80, 05C15 * Research supported in part by a USA Israeli BSF grant and by a grant from the Israel Science Foundation. t Research supported in part by a Charles Clore Fellowship.",

year = "1997",

doi = "10.1007/BF01215914",

language = "English (US)",

volume = "17",

pages = "303--313",

journal = "Combinatorica",

issn = "0209-9683",

publisher = "Janos Bolyai Mathematical Society",

number = "3",

}

TY - JOUR

T1 - The concentration of the chromatic number of random graphs

AU - Alon, Noga

AU - Krivelevich, Michael

N1 - Funding Information: Mathematics Subject Classification (1991): 05C80, 05C15 * Research supported in part by a USA Israeli BSF grant and by a grant from the Israel Science Foundation. t Research supported in part by a Charles Clore Fellowship.

PY - 1997

Y1 - 1997

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0031455112&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0031455112&partnerID=8YFLogxK

U2 - 10.1007/BF01215914

DO - 10.1007/BF01215914

M3 - Article

AN - SCOPUS:0031455112

SN - 0209-9683

VL - 17

SP - 303

EP - 313

JO - Combinatorica

JF - Combinatorica

IS - 3

ER -

The concentration of the chromatic number of random graphs

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this