0
$\begingroup$

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?

$\endgroup$
2
  • 2
    $\begingroup$ See this: cstheory.stackexchange.com/questions/17724/… $\endgroup$ – Austin Buchanan Jun 20 '13 at 20:53
  • 2
    $\begingroup$ 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. $\endgroup$ – Chandra Chekuri Jun 22 '13 at 14:58
2
$\begingroup$

A short answer is http://en.wikipedia.org/wiki/Graph_factorization. A more comprehensive reference might be the classic "Matching Theory" by Lovasz and Plummer, which is the best on this topic.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.