Packing cycles with modularity

Packing cycles with modularity

-
Paul Wollan, Universität Hamburg
Fine Hall 224

Erdős 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.