A linear bound for a connectivity partition in graphs
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