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 [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?

Solved b.jpg

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


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.


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