Packing cycles with modularity
Packing cycles with modularity
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.