Given a graph G=(V,E) and a family H of graphs, a subgraph G' of G is usually called an H-factor, if it is a spanning subgraph of G and its every component is isomorphic to some member of H. Here we focus on the case K_2 \in H. Many nice results are known in the literature for this case. We show some very general theorems (Tutte type existence theorem, Tutte-Berge type minimax formula, Gallai-Edmonds type structure theorem) that can be considered as a common generalization of almost all such known results. In this paper we use a stricter and more general concept for H-factors, namely where the components of G' must be induced subgraphs of G.
Keywords:
matching, factor, structure theorem, matroid
Bibtex entry:
@techreport{egres-02-07,
AUTHOR | = | {Kir{\'a}ly, Zolt{\'a}n and Szab{\'o}, J{\'a}cint}, |
TITLE | = | {Generalized induced factor problems}, |
NOTE | = | {{\tt egres.elte.hu}}, |
INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
YEAR | = | {2002}, |
NUMBER | = | {TR-2002-07} |