Generalized edge packings (Q1825138)

In an undirected graph G a generalized edge packing is a collection of (not necessarily edge-disjoint) chains of odd length such that all chains have distinct endpoints. Previously, edge disjoint generalized edge packings, called odd chain packings, having been discussed by the author [Discrete Math. 51, 319-321 (1984; Zbl 0545.05049)] and \textit{W. R. Pulleyblank} and the author [Odd chain packings, to appear in Eur. J. Comb.]. In particular, finding a maximum odd chain packing is known to be polynomially reductible to finding a maximum capacitated b-matching. Obviously, matchings are odd chain packings. Here, basic properties of matchings are generalized to generalized edge packings, e.g. the augmenting chain theorem, matching matroids, and the Berge-Norman-Rabin theorem on matchings and node coverings. Although reformulations of some of the problems studied as capacitated b-matching problems are possible, simple and direct derivations independent of b-matching theory are given. For bipartite graphs, min-max results analogous to the theorem of König on matchings can be proved using elementary network flow techniques.