Published in:
Electron. J. Combin. 12 (2005) 1
Generalizing Kaneko's long path packing problem, Hartvigsen, Hell and Szabó [2] consider a new type of undirected graph packing problem, called the k-piece packing problem. A k-piece is a simple, connected graph with highest degree exactly k, so when k=1 we get the classical matching problem. They give a polynomial algorithm, a Tutte-type characterization and a Berge-type minimax formula, but they leave open the question of a Gallai-Edmonds type structure theorem. This paper fills this gap by describing such a decomposition. We also prove that the vertex sets coverable by k-piece packings have a matroidal structure in a certain way.
Keywords:
Graph packing, Gallai-Edmonds decomposition, Matroid
Bibtex entry:
@techreport{egres-03-12,
AUTHOR | = | {Janata, Marek and Loebl, Martin and Szab{\'o}, J{\'a}cint}, |
TITLE | = | {A Gallai-Edmonds type theorem for the $k$-piece packing problem}, |
NOTE | = | {{\tt www.cs.elte.hu/egres}}, |
INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
YEAR | = | {2003}, |
NUMBER | = | {TR-2003-12} |