pith. sign in

arxiv: 1412.2894 · v2 · pith:A3HBZN7Vnew · submitted 2014-12-09 · 🧮 math.CO

Long cycles through prescribed vertices have the ErdH{o}s-P\'osa property

classification 🧮 math.CO
keywords cdotcyclesvertexleastadditionalgorithmcardinalitycontain
0
0 comments X
read the original abstract

We prove that for every graph, any vertex subset $S$, and given integers $k,\ell$: there are $k$ disjoint cycles of length at least $\ell$ that each contain at least one vertex from $S$, or a vertex set of size $O(\ell \cdot k \log k)$ that meets all such cycles. This generalises previous results of Fiorini and Hendrickx and of Pontecorvi and Wollan. In addition, we describe an algorithm for our main result that runs in $O(k \log k \cdot s^2 \cdot (f(\ell) \cdot n+m))$ time, where $s$ denotes the cardinality of $S$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.