×

The decomposability of additive hereditary properties of graphs. (English) Zbl 0982.05082

Summary: An additive hereditary property of graphs is a class of simple graphs which is closed under unions, subgraphs and isomorphisms. If \({\mathcal P}_1,\dots,{\mathcal P}_n\) are properties of graphs, then a \(({\mathcal P}_1,\dots, {\mathcal P}_n)\)-decomposition of a graph \(G\) is a partition \(E_1,\dots, E_n\) of \(E(G)\) such that \(G[E_i]\), the subgraph of \(G\) induced by \(E_i\), is in \({\mathcal P}_i\), for \(i= 1,\dots, n\). We define \({\mathcal P}_1\oplus\cdots\oplus {\mathcal P}_n\) as the property \(\{G\in{\mathcal I}: G\) has a \(({\mathcal P}_1,\dots,{\mathcal P}_n)\)-decomposition}. A property \({\mathcal P}\) is said to be decomposable if there exist non-trivial hereditary properties \({\mathcal P}_1\) and \({\mathcal P}_2\) such that \({\mathcal P}={\mathcal P}_1\oplus{\mathcal P}_2\). We study the decomposability of the well-known properties of graphs \({\mathcal I}_k\), \({\mathcal O}_k\), \({\mathcal W}_k\), \({\mathcal I}_k\), \({\mathcal S}_k\), \({\mathcal D}_k\) and \({\mathcal O}^p\).

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDFBibTeX XMLCite
Full Text: DOI