Kawarabayashi–Ozeki conjecture on disjoint paths preserving connectivity

Let kk and ll be positive integers. A graph is rr-connected if deleting fewer than rr vertices leaves it connected. For a graph GG and paths P1,,PkP_1,\ldots,P_k, write Gi=1kV(Pi)G-\bigcup_{i=1}^k V(P_i) for the graph obtained by deleting all vertices on those paths.

Kawarabayashi–Ozeki conjecture. There exists a function f(k,l)f(k,l) such that, for every f(k,l)f(k,l)-connected graph GG and two distinct vertices ss and tt in GG, there are kk internally disjoint paths P1,,PkP_1,\ldots,P_k with endpoints ss and tt such that

Gi=1kV(Pi)G-\bigcup_{i=1}^k V(P_i)

is ll-connected.

This conjecture strengthens the cited result that, after deleting one induced path between two specified vertices from a sufficiently highly connected graph, the remainder can be required to be kk-connected. It asks whether a bounded connectivity assumption likewise permits deleting several internally disjoint sstt paths while retaining prescribed connectivity.

Sources & referencesView supporting material

Primary source

Rose McCarty, Yan Wang and Xingxing Yu, “7-Connected Graphs are 4-Ordered”, arXiv:1808.05124 (2019).

Additional references

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.