On some simple degree conditions that guarantee the upper bound on the chromatic (Choice) number of random graphs

is well known that almost every graph in the random space G(n, p) has chrom atic number of order O (n;Dl log(np)), but it is not clear how we can recog nize such graphs without eventually computing the chromatic numbers, which is NP-hard. The first goal of this article is to show that the above-mentio ned upper bound on the chromatic number can be guaranteed by simple degree conditions, which are satisfied by G(n,p) almost surely for most values of p. It turns out that the same conditions imply a similar bound for the choi ce number of a graph. The proof implies a polynomial coloring algorithm for the case p is not too small. magnitude of the choice number of random grap hs and hypergraphs. It also leads to a general bound on the choice number o f locally sparse graphs and to several interesting facts about finite field s. (C) 1999 John Wiley & Sons, Inc.