Partitioning edge-connectivity
By the Nash-Williams/Tutte theorem ([NW] or [T]) on disjoint spanning trees, the above conjecture is true if is -edge-connected. This is the only partial result I know of. Here is a related conjecture.
The values and are of no special importance in the above conjecture. Indeed, an affirmative answer to the above problem with and replaced by and for any would still be valuable - and in particular, would imply the 2+epsilon flow conjecture.
Definition: Let be a graph and let be a partition of . We say that is -courteous if is -edge-connected for every .
It is known (see [DJS]) that . It would be quite interesting if the truth were in fact . An improvement on the current upper bound would have some consequences for certain flow problems and cycle-cover problems. In general, one may define a function so that is the smallest integer (or if none exists) so that every -edge-connected graph has a -courteous coloring of size . It is known (see [DJS]) that , and that . Two special cases when better values are known are and .
Bibliography
[DJS] M. DeVos, T. Johnson, P.D. Seymour, Cut-coloring and circuit covering
[Ed] J. Edmonds, Minimum Partition of a Matriod into Independent Subsets, J. Res. Nat. Bur. Standards 69B (1965) 67-72. MathSciNet
[NW] C.S.J.A. Nash-Williams, Edge Disjoint Spanning Trees of Finite Graphs, J. London Math. Soc. 36 (1961) 445-450. MathSciNet
[T] W.T. Tutte, On the problem of decomposing a graph into n connected factors, J. London Math. Soc. 36 (1961), 221-230. MathSciNet
* indicates original appearance(s) of problem.