TR-2002-07

Generalized induced factor problems

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



Abstract

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}
}


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