id: 06065726
dt: j
an: 06065726
au: Kakimura, Naonori; Kawarabayashi, Ken-Ichi
ti: Packing cycles through prescribed vertices under modularity constraints.
so: Adv. Appl. Math. 49, No. 2, 97-110 (2012).
py: 2012
pu: Elsevier Science (Academic Press), San Diego, CA
la: EN
cc: 
ut: disjoint cycles; even cycles; feedback vertex sets; Erdős; Pósa property
ci: 
li: doi:10.1016/j.aam.2012.03.002
ab: Summary: The well-known theorem of Erdős-Pósa says that either a graph
    $G$ has $k$ disjoint cycles or there is a vertex set $X$ of order at
    most $f(k)$ for some function $f$ such that $G \setminus X$ is a
    forest. Starting with this result, there are many results concerning
    packing and covering cycles in graph theory and combinatorial
    optimization. In this paper, we present a common generalization of the
    following Erdős-Pósa properties: { indent=6mm \item{1.)}The
    Erdős-Pósa property for cycles of length divisible by a fixed integer
    $p$. \item{2.)}The Erdős-Pósa property for $S$-cycles, i.e., cycles
    which contain a vertex of a prescribed vertex set $S$. } Namely, given
    integers $k,p$, and a vertex set $S$ (whose size may not depend on $k$
    and $p$), we prove that either a graph $G$ has $k$ disjoint $S$-cycles,
    each of which has length divisible by $p$, or $G$ has a vertex set $X$
    of order at most $f(k,p)$ such that $G \setminus X$ has no such a
    cycle.
rv: