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.

matching, factor, structure theorem, matroid

Bibtex entry:

AUTHOR = {Kir{\'a}ly, Zolt{\'a}n and Szab{\'o}, J{\'a}cint},
TITLE = {Generalized induced factor problems},
NOTE= {{\tt}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2002},
NUMBER = {TR-2002-07}

Last modification: 22.11.2022. Please email your comments to Tamás Király!