Unique factorization of compositive hereditary graph properties

A graph property is any class of graphs that is closed under isomorphisms. A graph property P is hereditary if it is closed under taking subgraphs; it is compositive if for any graphs G 1,G 2 . P there exists a graph G . P containing both G 1 and G 2 as subgraphs. Let H be any given graph on vertices . 1, ..., . n , n . 2. A graph property P is H-factorizable over the class of graph properties . if there exist P 1, ..., P n . . such that P consists of all graphs whose vertex sets can be partitioned into n parts, possibly empty, satisfying: 1. for each i, the graph induced by the i-th non-empty partition part is in P i , and 2. for each i and j with i . j, there is no edge between the i-th and j-th parts if . i and . j are non-adjacent vertices in H. If a graph property P is H-factorizable over . and we know the graph properties P 1, ..., P n , then we write P = H[P 1, ..., P n ]. In such a case, the presentation H[P 1, ..., P n ] is called a factorization of P over .. This concept generalizes graph homomorphisms and (P 1, ..., P n )-colorings. In this paper, we investigate all H-factorizations of a graph property P over the class of all hereditary compositive graph properties for finite graphs H. It is shown that in many cases there is exactly one such factorization.