ON THE USE OF AUGMENTING CHAINS IN CHAIN PACKINGS

In a graph G = (X,E), we assign to each node-upsilon a positive integer b(upsilon) less-than-or-equal-to d(G)(upsilon), where d(G)(upsilon) is the degree of upsilon in G. Let P be a collection of edge-disjoint chains such that no two chains in P have a common endpoint and such that in the partial graph H = (X,E(P)) formed by the edge set E(P) of P we have d(H)(upsilon) less-than-or-equal-to b(upsilon) for each node-upsilon. P is called a chain packing. We extend the augmenting chain theorem of matchings to chain packings and we find an analogue of matching matroids. We also study chain packings by short chains, i.e., chains of lengths one or two. We show that we may restrict ourselves to packings by short chains when we want to find a packing containing a maximum number of chains. We show that the use of augmenting chains fails in general to produce a new short chain packing from an old one, even for bipartite graphs, but that it does do so for the special case of trees. For the case of trees, we also find a min-max result for packings by short chains.