# Partitioning edge-connectivity

 Importance: Medium ✭✭
 Author(s): DeVos, Matt
 Subject: Graph Theory » Basic Graph Theory » » Connectivity
 Keywords: edge-coloring edge-connectivity
 Prize: bottle of wine (DeVos)
 Posted by: mdevos on: March 7th, 2007
Question   Let be an -edge-connected graph. Does there exist a partition of so that is -edge-connected and is -edge-connected?

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.

Conjecture   There exists a fixed integer so that every -edge-connected graph has a subset of edges with the property that every edge-cut of has between and of its edges in .

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 .

Problem   What is the smallest integer so that every 3-edge-connected graph has a 2-courteous coloring of size ?

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.