{"id":"arxiv/2610.09365","url":"https://arxiv.org/abs/2610.09365","tags":["math.CO"],"score":0,"title":"A linear bound for a connectivity partition in graphs","domain":"math.CO","source":"arxiv","authors":["Jia Zhou","Jin Yan","Yunshu Gao"],"reviews":0,"subject":"math.CO","summary":"Kühn and Osthus proved that, for every positive integer $\\ell$, every $2^{16}\\ell^2$-connected graph $G$ has a partition $V(G)=S\\cup T$ such that $G[S]$ and $G[T]$ are $\\ell$-connected and $d_T(v)\\geq \\ell$ for every $v\\in S$. And they asked whether the quadratic bound can be replaced by a linear bound. In this paper, we answer this question in the affirmative by proving that every $641\\ell$-connected graph $G$ has a partition $V(G)=S\\cup T$ such that $G[S]$ and $G[T]$ are $\\ell$-connected and $d_T(v)\\ge \\ell$ for every $v\\in S$. The proof integrates the Moser-Tardos resampling algorithm.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-07","reactions":{}}