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

About 2 years old · traced to

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(klog⁡k)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 G−BG(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.

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.