The Edmonds-Gallai decomposition for the \(k\)-piece packing problem (Q1773199)

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.