pipette
ESEspañol

A linear bound for a connectivity partition in graphs

Jia Zhou, Jin Yan, Yunshu Gao

Preprint

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