GENERALIZED CHROMATIC-NUMBERS OF RANDOM GRAPHS

Let P be a hereditary graph property. The P-chromatic number of a grap h is the minimal number of classes in a vertex partition wherein each class spans a subgraph with property P. For the property P of edgeless graphs the P-chromatic number is just the usual chromatic number, who se value is known to be (1/2 + o(1))n/log, n for almost every graph of order n. We show that we may associate with every nontrivial heredita ry property P an explicitly defined natural number r = r(B), and that the P-chromatic number is then (1/2r + o(1))n/log(2) n for almost ever y graph of order n. (C) 1995 John Wiley and Sons, Inc.