Kriesell’s Conjecture

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 $G(V,E)$ has $k$ edge-disjoint spanning trees if and only if $E(P) \geq k(|P|-1)$ for every partition $P$ of $V$ into non-empty classes, where $E(P)$ denotes the number of edges connecting distinct classes of $P$. One interesting corollary of this result is the following :

Theorem : Every $2k$-edge-connected graph has $k$ edge-disjoint spanning trees.

Let $G(V,E)$ be an undirected multigraph and $S \subseteq V$. An $S-tree$ is a tree of $G$ that contains every vertex in $S$. An $S-cut$ is a subset of edges whose removal disconnects some vertices in $S$. A graph is $k-S-connected$ if every $S-cut$ has at least $k$ edges. Kriesell conjectured the following generalization of the above theorem.

Kriesell’s conjecture : If $G$ is $2k-S-connected$, then $G$ has $k$ edge-disjoint $S-trees$.

The first breakthrough towards proving Kriesell’s conjecture was by Lau. He proved that if G is $24k$-edge-connected in $T$ then it has $k$ edge-disjoint Steiner trees. Recently, West and Wu [pdf] proved that it suﬃces for $S$ to be $6.5k$-edge-connected in $G$.

Open Problems

1. Obvious open problem is to prove or disprove Kriesell’s conjecture.
2. 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 factorsJ. 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