ON THE SIZE OF HEREDITARY CLASSES OF GRAPHS

A hereditary property of graphs is a class of graphs which is closed u nder taking induced subgraphs. For a hereditary property P, let P(n) d enote the set of P graphs on n labelled vertices. Clearly we have 0 le ss-than-or-equal-to \P(n)\ less-than-or-equal-to 2-n(n-1)/2, but much more can be said. Our main results show that the growth of \P(n)\ is f ar from arbitrary and that certain growth rates are impossible. For ex ample, for no property P does one have \P(n)\ approximately log n. (C) 1994 Academic Press, Inc.