The speed of hereditary properties of graphs

Given a property P of graphs, write P-n for the set of graphs with vertex s et [n] having property P. The growth or speed of a property P can be discus sed in terms of the values of \P-n\. For properties with \P-n\ < n(n) hered itary properties are surprisingly well determined by their speeds. Sharpeni ng results of E. R. Scheinerman and J. Zito (1994, J. Combin. Theory Ser. B 61, 16-39), we prove numerous results about the possible functions \P-n\ a nd describe in derail the properties exhibiting each type of growth. We als o list minimal properties exhibiting each type of growth. (C) 2000 Academic Press.