THE CHROMATIC-NUMBERS OF RANDOM HYPERGRAPHS

For a pair of integers 1 less than or equal to gamma <r, the gamma-chr omatic number of an r-uniform hypergraph H = (V, E) is the minimal k, for which there exists a partition of V into subsets T-1,..., T-k such that /e boolean AND T-i/ less than or equal to gamma for every e is a n element of E. In this paper we determine the asymptotic behavior of the gamma-chromatic number of the random r-uniform hypergraph H-r(n,p) for all possible values of gamma and for all values of p down to p = Theta(n(-r+1)). (C) 1998 John Wiley & Sons, Inc. Inc.