The long-cycle induced Erdős–Pósa conjecture
The long-cycle induced Erdős–Pósa conjecture
For a graph , an induced packing of cycles is a collection of cycles with no edge between distinct cycles. For a vertex set , let be its closed distance-one neighborhood. The long-cycle induced Erdős–Pósa conjecture. There exists a function such that, for all integers and , every graph contains either an induced packing of cycles of length at least , or a set of at most vertices such that has no cycle of length at least . The conjecture is known when is constant, and the source explains that the order is best possible up to a multiplicative constant; the variable- case remains open.
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
Sign in to submit a solution.
No solutions have been posted yet.