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$)

  • $\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$ Jan 5 at 19:26


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.