# Partitioning a bipartite graph into proportional factors

Let G=(V,E) be a bipartite graph, and $c_1,\dots c_k$ positive reals whose sum is 1. Can E always be partitioned into k parts $E_1,\dots,E_k,$ so that for every $v \in V$ and every $i \in \{1,\dots,k\}$ we have $\lfloor c_i d_E(v) \rfloor \leq d_{E_i}(v) \leq \lceil c_i d_E(v) \rceil$?

## Remarks

This question was asked by Correa and Goemans [1]. They proved a weaker bound $\lfloor c_i d_E(v) \rfloor-2 \leq d_{E_i}(v) \leq \lceil c_i d_E(v) \rceil+2$. An alternative proof was found by Feige and Singh [2], who also showed that if only upper bounds or only lower bounds are considered, then $\pm 2$ can be replaced by $\pm 1$.

If $c_i=1/k$ for every i, then the statement follows from total unimodularity, see de Werra [3]. If k=2, then it follows from the theorem on Orientation with degree bounds. The case when G is regular is also easy, because we can partition E into regular subgraphs satisfying the condition.

## References

1. J.R. Correa, M.X. Goemans, Improved bounds on nonblocking 3-stage clos networks, SIAM Journal on Computing 37(3), 870-894 (2007), DOI link, author link
2. U. Feige, M. Singh, Edge coloring and decompositions of weighted graphs, Algorithms-ESA 2008, DOI link, author link
3. D. de Werra, Equitable colorations of graphs, Rev Fran Rech Oper. 5 (1971), 3-8. PDF link.