pipette
ENEnglish

An Erd\H{o}s-P\'osa theorem for induced packings of even cycles

Jungho Ahn, Lars Jaffke, O-joung Kwon, Paloma T. de Lima, Hyemi Park

Preprint

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