# 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!