\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
\nopagenumbers
\noindent
%
%
{\bf The Edmonds-Gallai Decomposition for the $k$-Piece Packing Problem}
%
%
\medskip
\noindent
%
%
{\bf Marek Janata, Martin Loebl and J\'acint Szab\'o}
%
%
\vskip 5mm
\noindent
%
%
%
%
Generalizing Kaneko's long path packing problem, Hartvigsen, Hell
and Szab\'o consider a new type of undirected graph packing problem,
called the {\it $k$-piece packing problem}. A $k$-piece is a
simple, connected graph with highest degree exactly $k$ so in the
case $k=1$ we get the classical matching problem. They give a
polynomial algorithm, a Tutte-type characterization and a Berge-type
minimax formula for the $k$-piece packing problem. However, they
leave open the question of an Edmonds-Gallai type decomposition.
This paper fills this gap by describing such a decomposition. We
also prove that the vertex sets coverable by $k$-piece packings have
a certain matroidal structure.

\bye

.