Additive and hereditary properties of graphs are uniquely factorizable into irreducible factors

A hereditary property of graphs is any class of graphs closed under isomorphism and subgraphs. Let 𝒫₁, 𝒫₂,…, 𝒫_n be hereditary properties of graphs. We say that a graph G has property 𝒫_1°𝒫_2°···_°𝒫_n if the vertex set of G can be partitioned into n sets V₁, V₂,…, V_n such that the subgraph of G induced by V_i belongs to 𝒫_i; i = 1, 2,…, n. A hereditary property is said to be reducible if there exist hereditary properties 𝒫₁ and 𝒫₂ such that ℛ = 𝒫_1°𝒫₂; otherwise it is irreducible. We prove that the factorization of a reducible hereditary property into irreducible factors is unique whenever the property is additive, i.e., it is closed under the disjoint union of graphs. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 44–53, 2000