Factorizations and characterizations of induced‐hereditary and compositive properties
Alastair Farrugia, Peter Mihók, R. Bruce Richter, Gabriel Semanišin · Journal of Graph Theory · 2005
Abstract 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 ${\cal P}$ and ${\cal Q}$ are properties, the product ${\cal P}\circ {\cal Q}$ 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 G[A] $\in {\cal P}$ and G[B] $\in {\cal Q}$ . 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