The induced Erdős–Pósa conjecture for S-cycles

About 2 years old · traced to

Let GG be a graph and S⊆V(G)S\subseteq V(G). An SS-cycle is a cycle containing a vertex of SS, and an induced packing is a collection of cycles with no edge between distinct cycles. The induced Erdős–Pósa conjecture for SS-cycles. There exists a function f(k)=O(klog⁡k)f(k)=\mathcal{O}(k\log k) such that, for every positive integer kk, every graph GG, and every S⊆V(G)S\subseteq V(G), GG contains either an induced packing of kk SS-cycles or a set XX of at most f(k)f(k) vertices such that G−BG(X,1)G-B_G(X,1) has no SS-cycle. This extends the paper's induced cycle duality by requiring every packed or surviving cycle to meet a prescribed vertex set. 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.