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

From papers

Let GG be a graph and SV(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(klogk)f(k)=\mathcal{O}(k\log k) such that, for every positive integer kk, every graph GG, and every SV(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 GBG(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.

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.