# “k-matching” in graphs [duplicate]

A matching in a graph is a set of edges that are pair-wise non-adjacent. IOW, each node involved in the matching appears in only one edge.

Now I am wondering is there a generalized'' concept of matching, such that it still refers to an edge-set, and each vertex involved can appear in at most $k$ edges in this edge-set, where $k \ge 2$ is a pre-specified positive integer.

If such concept does exist, what are some interesting and representative problems studied for that?

• – Austin Buchanan Jun 20 '13 at 20:53
• They are typically called b-matchings and are very well-studied. Most books on combinatorial optimization will give an introduction to this topic after treating matchings. You can check Schrijver's book for instance. – Chandra Chekuri Jun 22 '13 at 14:58