1
$\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

4
$\begingroup$

Here's a counter-example for $k= 4$.

Take $G = K_{2,2}$, specifically $G=(V, E)$ where $V=\{1,2,3,4\}$ and $E=\{(1,3), (1, 4), (2,3), (2,4)\}$.

Define $b^1$ by $b^1_1 = b^1_3 = 1$ and $b^1_2=b^1_4=0$. Define $b^2 = b^1$.

Define $b^3$ by $b^1_1 = b^1_3 = 0$ and $b^1_2=b^1_4=1$. Define $b^4 = b^3$.

Then there is just one $b^1$ matching (which is also the only $b^2$ matching), namely $\{(1,3)\}$.

Likewise there is just one $b^3$ matching (which is also the only $b^4$ matching), namely $\{(2,4)\}$.

But there is no way to decompose the graph into 4 parts, where the $i$th part is a $b^i$ matching. (Because, e.g., the first and second parts would both have to use the edge $(1, 3)$.)

The counter example extends directly to $k\ge 4$. I don't know about $k=3$.

$\endgroup$
1
  • 1
    $\begingroup$ Aaaaaaarggggggh $\endgroup$ Aug 12, 2021 at 21:13

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.