Linear-connectivity partition conjecture for highly connected digraphs

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 cktlc\cdot ktl-connected digraph DD with δ(D)nl\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.

Sources & referencesView supporting material

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.