In-degree bounded directed forests
From Egres Open
(Redirected from In-degree bounded arborescences)
The digraph D=(V,A) is the union of k directed forests and ϱ(v)≤kl for each v∈V. Is it true that D can be partitioned into k forests F1,…,Fk so that ϱFi(v)≤l for each i?
See the discussion page for a counterexample for k=2, l=2.
Remarks
The conjecture is due to A. Frank. For l=1 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 u:V→Z+. 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.