Linear-connectivity partition conjecture for highly connected digraphs
Linear-connectivity partition conjecture for highly connected digraphs
Let be a digraph of order , let , and let denote the minimum semidegree of . A digraph is strongly -connected if deleting fewer than vertices leaves it strongly connected.
Linear-connectivity partition conjecture. There exists a constant such that the vertices of every strongly -connected digraph with can be partitioned into parts such that each of and is a strongly -connected digraph.
The preceding result gives a weaker bound of order on the required connectivity. The conjecture asks whether this can be reduced to a quantity linear in , , and , 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
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.