TR-2002-07

Generalized induced factor problems

Zoltán Király, Jácint Szabó

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 www.cs.elte.hu/egres}},
INSTITUTION	=	{Egerv{\'a}ry Research Group, Budapest},
YEAR	=	{2002},
NUMBER	=	{TR-2002-07}

}