Factorizations and characterizations of induced‐hereditary and compositive properties

An Erratum has been published for this article in Journal of Graph Theory 50:261, 2005 . A graph property (i.e., a set of graphs) is hereditary (respectively, induced‐hereditary) if it is closed under taking subgraphs (resp., induced‐subgraphs), while the property is additive if it is closed under disjoint unions. If and are properties, the product consists of all graphs G for which there is a partition of the vertex set of G into (possibly empty) subsets A and B with GA] and GB] . A property is reducible if it is the product of two other properties, and irreducible otherwise. We show that very few reducible induced‐hereditary properties have a unique factorization into irreducibles, and we describe them completely. On the other hand, we give a new and simpler proof that additive hereditary properties have a unique factorization into irreducible additive hereditary properties J. Graph Theory 33 (2000), 44–53]. We also introduce analogs of additive induced‐hereditary properties, and characterize them in the style of Scheinerman Discrete Math. 55 (1985), 185–193]. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 11–27, 2005