West–Wu's conjecture on packing T-connectors

From papers

Let GG be a graph and TV(G)T\subseteq V(G) a set of terminals. A TT-connector is the union of a family of edge-disjoint TT-paths such that, after shortcutting the paths one by one, the resulting graph has connected induced subgraph on TT. The set TT is rr-edge-connected in GG if no edge-cut of size smaller than rr separates two vertices of TT.

West–Wu's conjecture. For every positive integer kk, if TT is 3k3k-edge-connected in GG, then GG admits kk pairwise edge-disjoint TT-connectors.

West and Wu introduced TT-connectors as a strengthening of Steiner trees. Their conjecture is refuted: the paper constructs infinitely many counterexamples for k=1k=1 and for every even kk. DeVos, McDonald and Pivotto proved the conclusion under the stronger hypothesis that TT is (6k+6)(6k+6)-edge-connected in GG.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Roman Čada, Adam Kabela, Tomáš Kaiser and Petr Vrána, “Packing T-connectors in graphs needs more connectivity”, arXiv:2308.07218 (2023).

Additional references

2 papers in this index state this conjecture (2013–2023). The statement above is taken from the most recent of them; the others are arXiv:1307.7621.

Solutions 0

No solutions have been posted yet.