On invariants of hereditary graph properties

The product P∘QP∘Q of graph properties P,QP,Q is the class of all graphs having a vertex-partition into two parts inducing subgraphs with properties PP and QQ, respectively. For a graph invariant ϕϕ and a graph property PP we define ϕ(P)ϕ(P) as the minimum of ϕ(F)ϕ(F) taken over all minimal forbidden subgraphs F   of PP. An invariant of graph properties ϕϕ is said to be additive with respect to reducible hereditary properties   if ϕ(P∘Q)=ϕ(P)+ϕ(Q)ϕ(P∘Q)=ϕ(P)+ϕ(Q) for every pair of hereditary properties P,QP,Q. In this paper, we provide necessary and sufficient conditions for invariants to be additive with respect to reducible hereditary graph properties. We prove that the subchromatic number, the degeneracy number and tree-width and some other invariants of hereditary graph properties satisfy those conditions.