Induced Graph Packing Problems

Let H{\mathcal{H}} be a set of undirected graphs. The induced H{\mathcal{H}} -packing problem in an input graph G is to find a subgraph Q of G of maximum size such that each connected component of Q is an induced subgraph of G and is isomorphic to some member of H{\mathcal{H}} . In this paper we focus on the case when H{\mathcal{H}} consists of factor-critical graphs and a certain family of ‘propellers’. Clarifying the methods developed in the related theory of non-induced graph packings, we show a Gallai–Edmonds type structure theorem and a Berge–Tutte type minimax formula. We also give an Edmonds type alternating forest algorithm for the case when H{\mathcal{H}} consists of a sequential set of stars and factor-critical graphs. This simplifies the related result of Egawa, Kano and Kelmans.