pipette
ESEspañol

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

In the authors' words

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.

Main resultThe abstract does not state a limitation.

Appeared: Monday, October 19. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: 38 pages, 5 figures