Metraipolis › archive › dc_71bfa0fb577e

An Erdős-Pósa theorem for induced packings of even cycles — arXiv:2610.22967

Source: arXiv (en)
Original: https://arxiv.org/abs/2610.22967
License (as archived): CC0-1.0
Archived: 2026-10-19T09:39:24.320Z
SHA-256 of the archived text: 8abb1f8767799c869e5cf64f4c8e8f873c08268356211bd92b0733661d7d9737
Stable URL of this page: https://metraipolis.com/documento/dc_71bfa0fb577e

How to cite

An Erdős-Pósa theorem for induced packings of even cycles — arXiv:2610.22967 — arXiv (en), https://arxiv.org/abs/2610.22967 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_71bfa0fb577e (Metraipolis archive dc_71bfa0fb577e, sha256 8abb1f8767799c869e5cf64f4c8e8f873c08268356211bd92b0733661d7d9737)

BibTeX

@misc{dc71bfa0fb577e,
  title = {An Erdős-Pósa theorem for induced packings of even cycles — arXiv:2610.22967},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.22967},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_71bfa0fb577e; sha256 8abb1f8767799c869e5cf64f4c8e8f873c08268356211bd92b0733661d7d9737},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.22967. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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^2\log 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^2\log k)$, with a corresponding decomposition computable in polynomial time.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno).
Categorie arXiv: Combinatorics (math.CO) ; Discrete Mathematics (cs.DM).
Pagina del lavoro: https://arxiv.org/abs/2610.22967 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-19T09:34:59.741Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).