2
$\begingroup$

Any $r$-regular bipartite graph can be partitioned into $r$ disjoint perfect matchings. I want to know whether a version of this extends to perfect $b$-matchings.

Suppose we have a bipartite graph $G = (V,E)$. Given a vector $b \in \mathbb{Z}^V$, a perfect $b$-matching is an edge-subgraph $E'$ such that each vertex $v$ in $(V,E')$ has degree exactly $b_v$.

Now I have a bipartite graph and a collection of vectors $b^1, \ldots, b^k$. I am guaranteed that for each $b^i$, there exists a perfect $b^i$ matching in my graph, and that $deg(v) = \sum_{i=1}^k b^i_v$ for all $v$.

Question: Can I partition the edges of my bipartite graph into $k$ parts, where for each $i$, the i'th part is a perfect $b^i$-matching?

Attempt: I have proved this for $k=2$. Indeed, I can immediately remove the guaranteed $b_1$ matching, and because of the degree condition, the remaining edges will form a perfect $b_2$-matching.

However, the cases for $k \geq 3$ is unclear to me.... I suspect it is false. Does anyone know one way or the other?

Thank you for your help

$\endgroup$

1 Answer 1

1
$\begingroup$

It is false.

Take $K_{2,2}$ with vertices in one part $\{x_1,x_2\}$ and the other $\{y_1,y_2\}$. Let $b^i(x_i) = b^i(y_i) = 1$ and $b^i(x_{3-i}) = b^i(y_{3-i}) = 0$ for $i=1,2$. Let $b^3 = b^1$ and $b^4 = b^2$. Then $b^1, b^2, b^3, b^4$ satisfy the requirements (there exists $b^i$-matchings for each $i$ and they sum to the degrees), but $b^1$ and $b^3$ matchings are never disjoint.

$\endgroup$
2
  • $\begingroup$ The $b^i$ vectors are supposed to have an entry for every vertex in the graph, but it seems like you have only specified the values on the $a_i$. $\endgroup$ Aug 11, 2021 at 16:29
  • $\begingroup$ My bad. I will correct it now. $\endgroup$ Aug 11, 2021 at 17:25

Your Answer

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

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