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 𝓟₁,𝓟₂, ...,𝓟ₙ.
A natural generalization of the fundamental graph vertex-colouring problem leads to the class of problems known as generalized or improper colourings. These problems can be very well described in the language of reducible (induced) hereditary properties of graphs. It turned out that a very useful tool for the unique determination of these properties are generating sets. In this paper we focus on the structure of specific generating sets which provide the base for the proof of The Unique Factorization Theorem for induced-hereditary properties of graphs.
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ć.