A linear bound for a connectivity partition in graphs
In the authors' words
K\"{u}hn and Osthus proved that, for every positive integer , every -connected graph has a partition such that and are -connected and for every . 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 -connected graph has a partition such that and are -connected and for every . The proof integrates the Moser-Tardos resampling algorithm.
Main resultThe abstract does not state a limitation.
Appeared: Thursday, October 8. arXiv. Preprint, not yet peer-reviewed.
Authors' comment: 9 pages