Partitioning edge-connectivity

Discussion

By the Nash-Williams/Tutte theorem ([NW] or [T]) on disjoint spanning trees, the above conjecture is true if $ G $ is $ 2(a+b) $ -edge-connected. This is the only partial result I know of. Here is a related conjecture. Conjecture There exists a fixed integer $ k $ so that every $ k $ -edge-connected graph $ G=(V,E) $ has a subset of edges $ S $ with the property that every edge-cut of $ G $ has between $ \frac{1}{3} $ and $ \frac{2}{3} $ of its edges in $ S $ . The values $ \frac{1}{3} $ and $ \frac{2}{3} $ are of no special importance in the above conjecture. Indeed, an affirmative answer to the above problem with $ \frac{1}{3} $ and $ \frac{2}{3} $ replaced by $ \frac{1}{t} $ and $ 1 - \frac{1}{t} $ for any $ t > 0 $ would still be valuable - and in particular, would imply the 2+epsilon flow conjecture . Definition: Let $ G=(V,E) $ be a graph and let $ P=\{E_1,E_2,...,E_t\} $ be a partition of $ E $ . We say that $ P $ is $ k $ -courteous if $ G \setminus E_i $ is $ k $ -edge-connected for every $ 1 \le i \le t $ . Problem What is the smallest integer $ t $ so that every 3-edge-connected graph has a 2-courteous coloring of size $ t $ ? It is known (see [DJS]) that $ 4 \le t \le 10 $ . It would be quite interesting if the truth were in fact $ t=4 $ . 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 $ H : {\mathbb Z}^2 \rightarrow {\mathbb Z} \cup \{\infty\} $ so that $ H(a,b) $ is the smallest integer $ t $ (or $ \infty $ if none exists) so that every $ a $ -edge-connected graph has a $ b $ -courteous coloring of size $ t $ . It is known (see [DJS]) that $ H(2k+2,2k+1) = \infty $ , and that $ 2k+1 < H(2k+1,2k) < C 100^k $ . Two special cases when better values are known are $ 2 < H(4,2) < 5 $ and $ 5 < H(5,4) < 31 $ .