A linear bound for a connectivity partition in graphs
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.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.09365
curl -X POST /api/v1/records/arxiv/2610.09365/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.09365/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'