| |
|
|
Abstract: The product P.Q of graph properties P;Q is a class of all graphs having a vertex-partition into two parts inducing subgraphs with properties P and Q, respectively. For a graph invariant ' and a graph property P we define '(P) as the minimum of '(F) taken over all minimal forbidden subgraphs F of P. An invariant of graph properties ' is said to be additive with respect to reducible hereditary properties if there is a constant c such that '(P.Q) = '(P)+'(Q)+c for every pair of hereditary properties P;Q. In this paper we provide a necessary and sufficient condition for invariants that are additive with respect to reducible hereditary graph properties. We prove that the order of the largest tree, the chromatic number, the colouring number, the tree-width and some other invariants of hereditary graph properties are of such type. Contact the authors: Peter.Mihok@tuke.sk, semanisin@science.upjs.sk Download PDF version of the preprint. |