RANDOM I-COLORABLE GRAPHS

In this article we investigate properties of the class of all l-colora ble graphs on n vertices, where l = l(n) may depend on n. Let G(n)l de note a uniformly chosen element of this class, i.e., a random l-colora ble graph. For a random graph G(n)l we study in particular the propert y of being uniquely l-colorable. We show that not only does there exis t a threshold function l = l(n) for this property, but this threshold corresponds to the chromatic number of a random graph. We also prove s imilar results for the class of all l-colorable graphs on n vertices w ith m = m(n) edges. (C) 1995 John Wiley & Sons, Inc.