Kawarabayashi–Ozeki conjecture on disjoint paths preserving connectivity
Kawarabayashi–Ozeki conjecture on disjoint paths preserving connectivity
Let and be positive integers. A graph is -connected if deleting fewer than vertices leaves it connected. For a graph and paths , write for the graph obtained by deleting all vertices on those paths.
Kawarabayashi–Ozeki conjecture. There exists a function such that, for every -connected graph and two distinct vertices and in , there are internally disjoint paths with endpoints and such that
is -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 -connected. It asks whether a bounded connectivity assumption likewise permits deleting several internally disjoint – 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.