PreprintarXiv licencearXiv
A linear bound for a connectivity partition in graphs
Abstract
Kühn and Osthus proved that, for every positive integer ℓ, every 216ℓ2-connected graph G has a partition V(G)=S∪ T such that G[S] and G[T] are ℓ-connected and dT(v)≥ ℓ for every v∈ 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ℓ-connected graph G has a partition V(G)=S∪ T such that G[S] and G[T] are ℓ-connected and dT(v)≥ ℓ for every v∈ S. The proof integrates the Moser-Tardos resampling algorithm.
Related
- The Complexity of Weak Partition Connectivity in Hedgegraphs
- Thermal Recurrence Orders of the Potts Model Partition Function in Grid Graphs
- Partition of unity a posteriori error estimators for the linear elasticity eigenvalue problem
- Partition regular linear equations over Sidon sets
- Higher-Order Fluctuations of the Log-Partition Function for Ising Models on Inhomogeneous Random Graphs
BibTeX
@misc{zhou2026linear,
title = {{A linear bound for a connectivity partition in graphs}},
author = {Jia Zhou and Jin Yan and Yunshu Gao},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.09365},
eprint = {2610.09365},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.09365},
}
RIS
TY - UNPB
TI - A linear bound for a connectivity partition in graphs
AU - Jia Zhou
AU - Jin Yan
AU - Yunshu Gao
PY - 2026
DA - 2026/10/07
PB - arXiv
DO - 10.48550/arxiv.2610.09365
UR - https://arxiv.org/abs/2610.09365
AB - Kühn and Osthus proved that, for every positive integer ℓ, every 2^16ℓ^2-connected graph G has a partition V(G)=S∪ T such that G[S] and G[T] are ℓ-connected and d_T(v)≥ ℓ for every v∈ 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ℓ-connected graph G has a partition V(G)=S∪ T such that G[S] and G[T] are ℓ-connected and d_T(v)≥ ℓ for every v∈ S. The proof integrates the Moser-Tardos resampling algorithm.
ER -