Extending a previous result by Erdös, Kleitman, and Rothschild, Kolaitis, Prömel and Rothschild proved in 1986 that a random K_k-free graph on n vertices is almost surely (k-1)-colorable. In this talk we consider the question whether a similar result holds for random K_k-free graphs on n vertices with a prescribed number m=m(n) of edges.
We show that the evolution of random K_k-free graphs exhibits two phase transitions with respect to being (k-1)-colorable as m increases from 0 to n^2: first it is almost surely (k-1)-colorable, then it is not, and then it is once again. In particular, we prove that there is a sharp threshold at t_k(n) = c_k n^{-2/(k+1)} (log n)^{2/(k^2-k-2)}. Our results hold provided the so-called KLR-Conjecture is true for K_k. The latter has been verified for K_3, K_4, and K_5.
Copyright. All Rights Reserved.