02161309

j

02161309 Janata, Marek Loebl, Martin Szab\'o, J\'acint The Edmonds-Gallai decomposition for the $k$-piece packing problem. Electron. J. Comb. 12, No. 1, Research paper R8, 21 p., electronic only (2005). 2005 Prof. Andr\'e K\"undgen, Deptartment of Mathematics, California State University San Marcos, San Marcos, CA EN barrier galaxy matching matroid

emis:journals/EJC/Volume_12/Abstracts/v12i1r8.html

A $k$-piece is a simple, connected graph with the highest degree exactly $k$. The $k$-piece packing of a graph $G$ is a subgraph $P$ of $G$ such that each connected component of $P$ is a $k$-piece. In the paper, an Edmonds-Gallai type decomposition for maximal $k$-piece packings is given. Moreover, it is proved that the vertex sets coverable by $k$-piece packings have a certain matroidal structure. Martin Knor (Bratislava)