THE DECOMPOSABILITY OF ADDITIVE HEREDITARY PROPERTIES OF GRAPHS

An additive hereditary property of graphs is a class of simple gra-phs which is closed under unions, subgraphs and isomorphisms. If P1,...,Pn are properties of graphs, then a (P1,...,Pn)-decomposition of a graph G is a partition E1,..., En of E(G) such that G[Ei], the sub-graph of G induced by Ei, is in Pi, for i = 1,..., n. We define P1⊕ · · ·⊕ Pn as the property {G ∈ I: G has a (P1,...,Pn)-decomposition}. A property P is said to be decomposable if there exist non-trivial he-reditary properties P1 and P2 such that P = P1 ⊕ P2. We study the decomposability of the well-known properties of graphs Ik, Ok, Wk, Tk, Sk, Dk and Op