The distance-packing Erdős–Pósa conjecture for cycles

From papers

For a positive integer dd, a distance-dd packing of cycles in a graph GG is a set of cycles such that no path of length at most dd joins two distinct cycles. For a vertex set XX, let BG(X,r)B_G(X,r) be the vertices at distance at most rr from XX. The distance-packing Erdős–Pósa conjecture. There are functions f(k)=O(klogk)f(k)=\mathcal{O}(k\log k) and g(d)=O(d)g(d)=\mathcal{O}(d) such that, for all positive integers k,dk,d, every graph GG contains either a distance-dd packing of kk cycles or a set XX of at most f(k)f(k) vertices such that GBG(X,g(d))G-B_G(X,g(d)) is a forest. This would simultaneously generalize the paper's induced-cycle and distance-dd two-cycle results. No resolution is given in the supplied text.

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.