Packing cycles with modularity constraints
Erdos and Posa proved that a there exists a function $f$ such that any graph
either has $k$ disjoint cycles or there exists a set of $f(k)$ vertices
that intersects
every cycle. The analogous statement is not true for odd cycles - there
exist numerous
examples of graphs that do not have two disjoint odd cycles, and yet no
bounded number of vertices intersects every odd cycle. However, Reed
has given a partial characterization of when there does not exist a
bounded size set of vertices intersecting every odd cycle.
We will discuss recent work on when a graph has many disjoint cycles of
non-zero length modulo $m$ for arbitrary $m$. When $m$ is odd, we see
that again there exists a function $f$ such that any graph either has
$k$ disjoint cycles of non-zero length modulo $m$ or there exists a set
of at most $f(k)$ vertices intersecting every such cycle of non-zero
length. When $m$ is even, no such function $f(k)$ exists. However, the
partial characterization of Reed can be extended to describe when a
graph has neither many disjoint cycles of non-zero length modulo $m$ nor
a small set of vertices intersecting every such cycle.