pipette
ENEnglish

A linear bound for a connectivity partition in graphs

Jia Zhou, Jin Yan, Yunshu Gao

Preprint

En palabras de los autores

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.

Resultado principalEl resumen no menciona limitaciones.

Apareció: jueves, 8 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: 9 pages