BETA-MATCHING DEGREE-SEQUENCE POLYHEDRA

A capacitated b-matching in a graph is an assignment of non-negative integers to edges, each at most a given capacity and the sum at each vertex at most a given bound. Its degree sequence is the vector whose components are the sums at each vertex. We give a linear-linequality description of the convex hull of degree sequences of capacitated b-matchings of a graph. This result includes as a special cases theorems of Balas-Pulleyblank on matchable sets and Korem on degree sequences of simple graphs. We also give a min-max separation theorem, and describe a connection with submodular functions.