Unique factorisation of additive induced-hereditary properties

الأصل · EN

An additive hereditary graph property is a set of graphs, closed under isomorphism and under taking subgraphs and disjoint unions. Let P₁, >..., Pₙ be additive hereditary graph properties. A graph G has property (P₁ ∘... ∘ Pₙ) if there is a partition (V₁,..., Vₙ) of V(G) into n sets such that, for all i, the induced subgraph G[Vᵢ] is in Pᵢ. A property P is reducible if there are properties Q, R such that P = Q ∘ R; otherwise it is irreducible. Mihók, Semanišin and Vasky [J. Graph Theory 33 (2000), 44--53] gave a factorisation for any additive hereditary property P into a given number dc(P) of irreducible additive hereditary factors. Mihók [Discuss. Math. Graph Theory 20 (2000), 143--153] gave a similar factorisation for properties that are additive and induced-hereditary (closed under taking induced-subgraphs and disjoint unions). Their results left open the possiblity of different factorisations, maybe even with a different number of factors; we prove here that the given factorisations are, in fact, unique.