Abstract
Let χ(G(n, p)) denote the chromatic number of the random graphG(n, p). We prove that there exists a constantd 0 such that fornp(n)>d 0,p(n)→0, the probability that
tends to 1 asn→∞.
Similar content being viewed by others
References
B. Bollobás: The chromatic number of random graphs,Combinatorica,8 (1988), 49–56.
A. M. Frieze: On the independence number of random graphs,Disc. Math.,81 (1990), 171–175.
D. Matula: Expose-and-merge exploration and the chromatic number of a random graph,Combinatorica,7 (1987), 275–284.
D. Matula, andL. Kučera: An expose-and-merge algorithm and the chromatic number of a random graph, in “Proceedings of Random Graphs '87”, Wiley, Chichester, 1990, 175–188.
E. Shamir, andJ. Spencer: Sharp concentration of the chromatic number on random graphsG n, p ,Combinatorica,7 (1987), 124–129