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

CC BY-SA 3.0
2013-06-20T20:52:36.377Z
2013-06-20T20:52:36.377Z
Yixin Cao
<p>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.  </p>

<p>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.</p>

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

CC BY-SA 3.0
2013-06-20T20:53:58.233Z
See this: http://cstheory.stackexchange.com/questions/17724/what-is-complexity-of-this-max-edge-subgraph-problem/17727#17727
Austin Buchanan
CC BY-SA 3.0
2013-06-22T14:58:51.147Z
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
<matching>
"k-matching" in graphs
user16416
# "k-matching" in graphs

(Asked by: username_0 on 2013-06-20)

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?

**Tags:** matching

> **Comments:**
> **username_1**: See this: http://cstheory.stackexchange.com/questions/17724/what-is-complexity-of-this-max-edge-subgraph-problem/17727#17727  
> **username_2**: 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.  

---

## 1 answers

### Answer by username_3 on 2013-06-20. Score: 2

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.


---

