A property of graphs is any class of graphs closed under isomorphism. A property of graphs is induced-hereditary and additive if it is closed under taking induced subgraphs and disjoint unions of graphs, respectively. Let 𝓟₁,𝓟₂, ...,𝓟ₙ be properties of graphs. A graph G is (𝓟₁,𝓟₂,...,𝓟ₙ)-partitionable (G has property 𝓟₁ º𝓟₂ º... º𝓟ₙ) if the vertex set V(G) of G can be partitioned into n sets V₁,V₂,..., Vₙ such that the subgraph $G[V_i]$ of G induced by V_i belongs to $𝓟_i$; i = 1,2,...,n. A property 𝓡 is said to be reducible if there exist properties 𝓟₁ and 𝓟₂ such that 𝓡 = 𝓟₁ º𝓟₂; otherwise the property 𝓡 is irreducible. We prove that every additive and induced-hereditary property is uniquely factorizable into irreducible factors. Moreover the unique factorization implies the existence of uniquely (𝓟₁,𝓟₂, ...,𝓟ₙ)-partitionable graphs for any irreducible properties 𝓟₁,𝓟₂, ...,𝓟ₙ.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.