The long-cycle induced Erdős–Pósa conjecture

From papers

For a graph GG, an induced packing of cycles is a collection of cycles with no edge between distinct cycles. For a vertex set XX, let BG(X,1)B_G(X,1) be its closed distance-one neighborhood. The long-cycle induced Erdős–Pósa conjecture. There exists a function f(k,)=O(k+klogk)f(k,\ell)=\mathcal{O}(k\ell+k\log k) such that, for all integers k1k\geq1 and 3\ell\geq3, every graph GG contains either an induced packing of kk cycles of length at least \ell, or a set XX of at most f(k,)f(k,\ell) vertices such that GBG(X,1)G-B_G(X,1) has no cycle of length at least \ell. The conjecture is known when \ell is constant, and the source explains that the order k+klogkk\ell+k\log k is best possible up to a multiplicative constant; the variable-\ell case remains open.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Jungho Ahn, J. Pascal Gollin, Tony Huynh and O-joung Kwon, “A coarse Erdős-Pósa theorem”, arXiv:2407.05883 (2025).

Solutions 0

No solutions have been posted yet.