GENERALIZED CHROMATIC-NUMBERS OF RANDOM GRAPHS

Given a hereditary (closed under taking induced subgraphs) class of graphs P, the P-chromatic number of a graph G, denoted chi(p)(G), is defined to be the least integer k such that V(G) admits a partition into k subsets each of which induce a member of P. The P-chromatic number of random graphs G on n vertices with fixed edge probability 0 < p < 1 is studied and it is shown that chi(p)(G) approximately cn in case \P\ < infinity and chi(p)(G) = THETA(n/log n) in case \P\ = infinity. Also considered are generalized edge chromatic numbers.