A Sharp Threshold fork-Colorability

Abstract

Let k be a fixed integer and fk(n, p) denote the probability that the random graph G(n, p) is k-colorable. We show that for k≥3, there exists dk(n) such that for any ϵ>0, (1) As a result we conclude that for sufficiently large n the chromatic number of G(n, d/n) is concentrated in one value for all but a small fraction of d>1. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 14, 63–70, 1999