Talk:In-degree bounded directed forests

False for k=2, l=2? -- Tamás Király 15:59, 17 December 2009 (UTC)

It seems to me that the conjecture is false for k=2 and l=2. There is a technical report by Fekete and Szabó, Uniform partitioning to bases in a matroid, where they show an example for the following:

There is a graph G partitionable to 2 spanning trees, and 4 independent nodes of degree 4, such that it is impossible to partition G into two spanning trees which have degree 2 in these 4 nodes.

The example is described at the beginning of Section 4. There is a minor error in the description - the edge pairs should be {ae,ab}, {ce,cd}, {bf,bc}, {df,da}, as indicated of Figure 1 of the technical report.

We can orient G so that the nodes [math]v_i[/math] have in-degree 4 (i=1,2,3,4). The conjecture would imply that this directed graph can be decomposed into 2 directed trees both of which have in-degree 2 in [math]v_i[/math] (i=1,2,3,4). However, this is impossible, since the underlying spanning trees would have degree 2 in these 4 nodes.

Please check if this counter-example is correct.

Re: False for k=2, l=2? -- Jácint Szabó 08:58, 30 September 2010 (UTC)

It seems correct. And thanks for pointing out the typo!