Does there exist an absolute constant C>0 such that, for every positive integer ell and every C ell-connected graph G, there is a partition V(G)=S mathbindot cupT such that G[S] and G[T] are ell-connected and d_T(v)≥ell for every v∈ S?

Kühn–Osthus connectivity-partition question

The Kühn–Osthus question asks whether sufficiently highly connected graphs admit the required two-part partition under a linear, rather than quadratic, connectivity hypothesis. A recent preprint claims the explicit bound $641\ell$ .

Known results

Kühn and Osthus established an earlier quadratic bound, written as $f(k)=O(k^{2})$ .
A later preprint proves an affirmative linear-bound theorem with some absolute constant $C>0$ , and records an intermediate $50k$ result for sufficiently large $k$ .

October 2026 linear-bound claim

Jia Zhou, Jin Yan, and Yunshu Gao claim that every $641\ell$ -connected graph has the required partition into two $\ell$ -connected induced subgraphs with the prescribed cross-degree condition. The claim appears in an unrefereed preprint and has not been independently verified in the retrieved sources.

Current status (as of October 2026): The existence of a linear bound is claimed in preprints, most recently with bound $641\ell$ , but that specific claim remains unverified.

Kühn–Osthus connectivity-partition question

Primary source

Additional references

Progress summary

Solutions 0