Long cycles through prescribed vertices have the Erdős‐Pósa property
Henning Bruhn, Felix Joos, Oliver Schaudt · Journal of Graph Theory · 2017
Abstract We prove that for every graph, any vertex subset S, and given integers : there are k disjoint cycles of length at least ℓ that each contain at least one vertex from S, or a vertex set of size that meets all such cycles. This generalizes previous results of Fiorini and Herinckx and of Pontecorvi and Wollan. In addition, we describe an algorithm for our main result that runs in time, where s denotes the cardinality of S.