Today’s short post is about Kriesell’s conjecture. In my first year of PhD I enjoyed reading several papers related to this cute conjecture.
Nash-Williams [N'61] and Tutte [Tutte'61] independently proved that a graph has edge-disjoint spanning trees if and only if for every partition of into non-empty classes, where denotes the number of edges connecting distinct classes of . One interesting corollary of this result is the following :
Theorem : Every -edge-connected graph has edge-disjoint spanning trees.
Let be an undirected multigraph and . An is a tree of that contains every vertex in . An is a subset of edges whose removal disconnects some vertices in . A graph is if every has at least edges. Kriesell conjectured the following generalization of the above theorem.
Kriesell’s conjecture : If is , then has edge-disjoint .
The first breakthrough towards proving Kriesell’s conjecture was by Lau. He proved that if G is -edge-connected in then it has edge-disjoint Steiner trees. Recently, West and Wu [pdf] proved that it suﬃces for to be -edge-connected in .
- Obvious open problem is to prove or disprove Kriesell’s conjecture.
- There a several related open problems about S-connectors in West-Wu’s paper.
- [Tutte'61] W.T.Tutte : On the problem of decomposing a graph into n connected factors, J. London Math. Soc. 36 (1961), 221–230.
- [N'61] C.St.J.A.Nash-Williams : Edge disjoint spanning trees of ﬁnite graphs, J. London Math. Soc. 36 (1961), 445–450.
- [Lau'07] L. C. Lau : An approximate max-Steiner-tree-packing min-Steiner-cut theorem. Combinatorica 27 (2007), 71–90