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

At least 1 year old · documented by

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ℓ+klog⁡k)f(k,\ell)=\mathcal{O}(k\ell+k\log k) such that, for all integers k≥1k\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 G−BG(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ℓ+klog⁡kk\ell+k\log k is best possible up to a multiplicative constant; the variable-ℓ\ell case remains open.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.