# In-degree bounded directed forests

The digraph *D=(V,A)* is the union of *k* directed forests and [math]\varrho(v)\leq kl[/math] for each [math]v\in V[/math]. Is it true that *D* can be partitioned into *k* forests [math]F_1,\dots,F_k[/math] so that [math]\varrho_{F_i}(v)\leq l[/math] for each *i*?

See the discussion page for a counterexample for *k*=2, *l*=2.

## Remarks

The conjecture is due to A. Frank. For [math]l=1[/math] the statement holds by Frank's theorem about covering by branchings ^{[1]}. A more general, analogous packing question is the following:

*Let *D=(V,A)* be a digraph, and [math]u: V \to {\mathbb Z_+}[/math]. When does *D* contain *k* edge-disjoint directed spanning trees so that in each directed spanning tree the in-degree of *v* is at most *u(v)*?*

The question of Recski considers the case *k=2*, the graph is the union of two spanning trees and exact values are prescribed for the in-degrees.

## References

- ↑ A. Frank,
*Covering Branchings*, Acta Scientiarum Mathematicarum [Szeged] 41 (1979), 77-81. Author link.