In-degree bounded directed forests

From Egres Open
Jump to: navigation, search

The digraph D=(V,A) is the union of k directed forests and ϱ(v)kl for each vV. Is it true that D can be partitioned into k forests F1,,Fk so that ϱFi(v)l for each i?


Solved b.jpg

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:VZ+. 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

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