Kühn–Osthus connectivity-partition question
Does there exist an absolute constant such that, for every positive integer and every -connected graph , there is a partition such that and are -connected and for every ?
References
- A linear bound for a connectivity partition in graphs — arXiv — Jia Zhou, Jin Yan, Yunshu Gao
Source: arXiv
Progress summary
An unrefereed preprint claims the quadratic requirement can be replaced by a linear one, but the new numerical bound has not been independently checked.
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 .
Known results
- Kühn and Osthus established an earlier quadratic bound, written as .
- A later preprint proves an affirmative linear-bound theorem with some absolute constant , and records an intermediate result for sufficiently large .
October 2026 linear-bound claim
Jia Zhou, Jin Yan, and Yunshu Gao claim that every -connected graph has the required partition into two -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 , but that specific claim remains unverified.
Sources
Solutions 0
No solutions have been posted yet.