An Erd\H{o}s-P\'osa theorem for induced packings of even cycles
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