A Gallai-Edmonds type theorem for the k-piece packing problem

Marek Janata, Martin Loebl, Jácint Szabó

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.

Graph packing, Gallai-Edmonds decomposition, Matroid

Bibtex entry:

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}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2003},
NUMBER = {TR-2003-12}

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