An Erd\H{o}s-P\'osa theorem for induced packings of even cycles
En palabras de los autores
We show that for every graph and every positive integer , contains either vertex-disjoint even cycles with no edges between distinct cycles, or a set of vertices whose closed neighborhood meets every even cycle of . Moreover, we give a polynomial-time algorithm that outputs one of the two outcomes. As an application, we show that every -free graph containing no induced packing of even cycles has tree-independence number , with a corresponding decomposition computable in polynomial time.
Resultado principalEl resumen no menciona limitaciones.
Apareció: lunes, 19 de octubre. arXiv. Preprint, todavía sin revisión por pares.
Comentario de los autores: 38 pages, 5 figures