A nice class for the vertex packing problem (Q1363736)

If \(v\) is a vertex of a graph \(G_2\), we can substitute a graph \(G_1\) for \(v\) by taking the vertex-disjoint union of \(G_1\) and \(G_2-v\), and adding an edge between every vertex of \(G_1\) and every vertex of \(G_2-v\) that was adjacent to \(v\). If \({\mathcal C}\) is a class of graphs, let \({\mathcal C}^*\) denote the smallest class of graphs containing \({\mathcal C}\) and closed under substitution. The authors call a class \({\mathcal C}\) of graphs nice if membership in the class can be certified in polynomial time. If \({\mathcal C}\) is a nice class of graphs and \(G\) is an arbitrary graph, consider the question `Does \(G\) belong to \({\mathcal C}^*\)?' The authors show that the preceding question can be answered in polynomial time whenever a forbidden subgraph characterization of \({\mathcal C}^*\) is known. The authors provide a forbidden subgraph characterization for \({\mathcal C}^*\) when \({\mathcal C}\) is the class of graphs that are claw-free or bipartite.