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 suffices for
to be
-edge-connected in
.
Open Problems
- 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.
References :
- [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 finite 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