Linear-connectivity partition conjecture for highly connected digraphs

About 13 years old · traced to

Let DD be a digraph of order nn, let k,t,lobreak be positive integersk,t,l obreak\text{ be positive integers}, and let δ(D)\delta(D) denote the minimum semidegree of DD. A digraph is strongly rr-connected if deleting fewer than rr vertices leaves it strongly connected.

Linear-connectivity partition conjecture. There exists a constant c>0c>0 such that the vertices of every strongly c⋅ktlc\cdot ktl-connected digraph DD with δ(D)≥n−l\delta(D)\geq n-l can be partitioned into tt parts V1,V2,…,VtV_1,V_2,\ldots,V_t such that each of D[V1],…,D[Vt]D[V_1],\ldots,D[V_t] and D[V1,…,Vt]D[V_1,\ldots,V_t] is a strongly kk-connected digraph.

The preceding result gives a weaker bound of order Ω(k3l2t2log⁡(2kl))\Omega(k^3l^2t^2\log(2kl)) on the required connectivity. The conjecture asks whether this can be reduced to a quantity linear in kk, tt, and ll, and is motivated by related partition results for highly connected digraphs.

References

Primary source

Yuzhen Qi, Jin Yan and Jia Zhou, “Bipartitions with prescribed order of highly connected digraphs”, arXiv:2402.16593 (2024).

Additional references

3 papers in this index state this conjecture (2013–2024). The statement above is taken from the most recent of them; the others are arXiv:2205.10871, arXiv:1309.7677.

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.