Skip to content
DraconiticResearch
Search Sources API
203,203 studies31 sourcesUpdated 33 min ago
PreprintarXiv licencearXiv

An Erdős-Pósa theorem for induced packings of even cycles

  • Jungho Ahn
  • Lars Jaffke
  • O-joung Kwon
  • Paloma T. de Lima
  • Hyemi Park
Open at sourcePDFDOICite

Abstract

We show that for every graph G and every positive integer k, G contains either k vertex-disjoint even cycles with no edges between distinct cycles, or a set of O(k2log k) vertices whose closed neighborhood meets every even cycle of G. Moreover, we give a polynomial-time algorithm that outputs one of the two outcomes. As an application, we show that every K1,t-free graph containing no induced packing of k even cycles has tree-independence number O(tk2log k), with a corresponding decomposition computable in polynomial time.

Related

  1. Erdös–Pósa property of cycles that are far apart
    Vida Dujmović, Gwenaël Joret, Piotr Micek +1
    Journal of the London Mathematical SocietyPeer-reviewedLicence not statedFull text10 citedCombinatorics & discrete mathematicsOpenAlex
  2. Hypergraph Universality and Erdos-Posa Failure for Chromatically Rich Odd Cycles
    Shuyan Chen
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. The coarse Erdős-Pósa theorem
    Sandra Albrechtsen, Marthe Bonamy, Romain Bourneuf +1
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsGeometry & topologyarXiv
  4. The Erdős-Pósa Property for Colorful Minors
    Evangelos Protopapas, Dimitrios M. Thilikos, Sebastian Wiederrecht
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. A Polynomial Erdős-Pósa bound for Eulerian digraphs
    Esther Galby, Roohani Sharma, Bart van der Steenhoven
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{ahn2026erdőspósa,
  title = {{An Erdős-Pósa theorem for induced packings of even cycles}},
  author = {Jungho Ahn and Lars Jaffke and O-joung Kwon and Paloma T. de Lima and Hyemi Park},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.22967},
  eprint = {2610.22967},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.22967},
}
RIS
TY  - UNPB
TI  - An Erdős-Pósa theorem for induced packings of even cycles
AU  - Jungho Ahn
AU  - Lars Jaffke
AU  - O-joung Kwon
AU  - Paloma T. de Lima
AU  - Hyemi Park
PY  - 2026
DA  - 2026/10/16
PB  - arXiv
DO  - 10.48550/arxiv.2610.22967
UR  - https://arxiv.org/abs/2610.22967
AB  - We show that for every graph G and every positive integer k, G contains either k vertex-disjoint even cycles with no edges between distinct cycles, or a set of O(k^2log k) vertices whose closed neighborhood meets every even cycle of G. Moreover, we give a polynomial-time algorithm that outputs one of the two outcomes. As an application, we show that every K_1,t-free graph containing no induced packing of k even cycles has tree-independence number O(tk^2log k), with a corresponding decomposition computable in polynomial time.
ER  -