Extension of hereditary classes with substitutions
A substitution of graph \(H\) in graph \(G\) instead of a vertex \(v\in V(G)\) is the graph consisting of the disjoint union of \(H\) and \(G-v\) with additional edge-set \(\{xy\mid x\in V(H)\) and \(y\in N_G(v)\}\), where \(N_G(v)= N(x)\) of all vertices \(v\) in \(G\) adjacent to \(x\). For a class \({\mathcal P}\) of graphs, its substitutional closure \({\mathcal P}^*\) consists of all graphs that can be obtained from \({\mathcal P}\) by repeated substitutions. Let \(\text{ISub}(G)\) be the set of all induced subgraphs of a graph \(G\). A class of graphs \({\mathcal P}\) is called hereditary if \(\text{ISUB}(G)\subseteq{\mathcal P}\) for every \(G\in{\mathcal P}\). A graph \(F\) is a minimal forbidden induced subgraph for a hereditary class \({\mathcal P}\) if \(\text{ISub}(F)\setminus{\mathcal P}= \{F\}\). The author proposes a method of constructing forbidden induced subgraphs for \({\mathcal P}^*\).
scientific article; zbMATH DE number 1925301