In this paper, we prove that random graphs only have trivial stable colorin
gs. Our result improves Theorem 4.1 in [Proc. 20th IEEE Symp. on Foundation
s of Comput. Sci., 1979, pp. 39-46]. It can be viewed as an effective versi
on of Corollary 2.13 in [SIAM J. Comput. 29 (2) (2000) 590-599]. As a bypro
duct, we also give an upper bound of the size of induced regular subgraphs
in random graphs. (C) 2002 Elsevier Science B.V. All rights reserved.