0
$\begingroup$

It is easy to see that symmetric difference of two matchings are cycles or simple paths. But what about b-matchings? Is there anything known about how they look? Even for restricted cases such as bipartite graphs $G=(U,V,E)$ with $b(v)=1\ \ \forall v\in U $

$def: b-matching$: Given a graph $G=(V,E)$ and an upper bound $b:V\to \mathbb{Z}^+$ for each vertex, a $b-matching$ is a sub-graph $H$ of $G$ such that $deg_H(v) \le b(v) \ \ \forall v\in V$. (Regular matching is a special case when $b(v)=1$)

Improve this question
$\endgroup$
1
  • $\begingroup$ My intuition is that the union (and likely also the symmetric difference) of three or more matchings can be very complicated. For example, Conjecture 2 in this paper is that every cubic, bridgeless graph is the union of 5 perfect matchings. $\endgroup$
    – Chris Jones
    Jan 5 at 19:26

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.