On invariants of hereditary graph properties (Q868369)

A hereditary property of graphs is a class \(\mathcal{P}\) of graphs that contains all isomorphs and subgraphs of its elements. Such a property is determined by its minimal forbidden graphs, those graphs that do not belong to \(\mathcal{P}\) but whose proper subgraphs all do. If \(\mathcal{P}\) and \(\mathcal{Q}\) are graph properties then their product \(\mathcal{P}\circ \mathcal{Q}\) is defined by: \(G\in \mathcal{P}\circ \mathcal{Q}\) if \(V(G)\) can be partitioned into two subsets \(V_{1}\) and \(V_{2}\) with corresponding induced subgraphs \(G_{1}\in \mathcal{P}\) and \(G_{2}\in \mathcal{Q}\). If \(\varphi \) is an integer-valued invariant of graphs and \(\mathcal{P}\) is a hereditary property then \(\varphi (\mathcal{P})\) is defined to be the minimum value of \(\varphi \) on the minimal forbidden graphs of \(\mathcal{P}\). Under certain natural conditions, the authors characterize the invariants which are additive (i.e., \(\varphi (\mathcal{P}\circ \mathcal{Q})=\varphi ( \mathcal{P})+\varphi (\mathcal{Q})\)) for all hereditary properties \(\mathcal{ P},\mathcal{Q}\). They use this characterization to show that the degeneracy number and the tree-width are both additive with respect to hereditary properties.