# Partitioning a bipartite graph into proportional factors

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

## Remarks

This question was asked by Correa and Goemans ^{[1]}. They proved a weaker bound [math]\lfloor c_i d_E(v) \rfloor-2 \leq d_{E_i}(v) \leq \lceil c_i d_E(v) \rceil+2[/math]. 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 [math]\pm 2[/math] can be replaced by [math]\pm 1[/math].

If [math]c_i=1/k[/math] 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

- ↑ 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 - ↑ U. Feige, M. Singh,
*Edge coloring and decompositions of weighted graphs*, Algorithms-ESA 2008, DOI link, author link - ↑ D. de Werra,
*Equitable colorations of graphs*, Rev Fran Rech Oper. 5 (1971), 3-8. PDF link.