Metraipolis › archive › dc_428600e697e0

A linear bound for a connectivity partition in graphs — arXiv:2610.09365

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.09365
License (as archived)
CC0-1.0
Archived
2026-10-08T12:43:54.534Z
SHA-256 of the archived text
3d5bcd3b5b422a6086d3f68938566d648428be67809aa6898041f99746194dbd
Stable URL of this page
https://metraipolis.com/documento/dc_428600e697e0

How to cite

A linear bound for a connectivity partition in graphs — arXiv:2610.09365 — arXiv (en), https://arxiv.org/abs/2610.09365 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_428600e697e0 (Metraipolis archive dc_428600e697e0, sha256 3d5bcd3b5b422a6086d3f68938566d648428be67809aa6898041f99746194dbd)
BibTeX
@misc{dc428600e697e0,
  title = {A linear bound for a connectivity partition in graphs — arXiv:2610.09365},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.09365},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_428600e697e0; sha256 3d5bcd3b5b422a6086d3f68938566d648428be67809aa6898041f99746194dbd},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.09365. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2610.09365 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-08T12:17:00.181Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).