科研速览 · Science Skim继续刷下去 · Keep skimming →
◇ arXiv2026-08-23· math.CO

Erdős-Pósa property for induced packings of long $S$-cycles

Jungho Ahn, O-joung Kwon

原始摘要(英文原文)· Original abstract
The Erdős-Pósa theorem states that for every integer $k\geq1$, every graph contains either $k$ vertex-disjoint cycles or a set of $\mathcal{O}(k\log k)$ vertices meeting all cycles. This fundamental min-max duality has been extended to numerous settings, including long cycles, $S$-cycles, that is, cycles containing a vertex in a prescribed set $S$, and cycles satisfying various additional constraints. In contrast, much less is known when the packing itself is required to be induced, namely, when distinct cycles are vertex-disjoint and have no edges between them. We prove that long $S$-cycles admit an induced version of the Erdős-Pósa-type duality. More precisely, we show that there exists a polynomial function $f(k,\ell)$ such that for all integers $k\geq1$ and $\ell\geq3$, every graph contains either an induced packing of $k$ $S$-cycles of length at least $\ell$ or a set of at most $f(k,\ell)$ vertices whose closed neighbourhood intersects all $S$-cycles of length at least $\ell$. The proof introduces a new ear-decomposition technique based on fragile ears and yields a polynomial-time algorithm for every fixed $\ell$.
读原文 · Read the paper ↗

AI 追问PRO

登录后使用 AI 追问

讨论区

登录后参与讨论

相关论文 · Related

Erdős-Pósa property for induced packings of long $S$-cycles — 科研速览 Science Skim