Title: A unified Erd\H os-P\'osa theorem for constrained cycles
Speaker: | Tony Huynh |
Affiliation: | Universite Libre de Bruxelles |
Room: | MC 5417 |
Abstract: In 1962, Erd\H os and P\'osa proved that for every positive integer $k$, there exists a constant $f(k)$ such that every graph $G$ either contains $k$ vertex-disjoint cycles or a set $X$ of at most $f(k)$ vertices such that $G-X$ contains no cycle. This theorem has since been generalized to cycles satisfying further constraints. For example, odd cycles, $S$-cycles, long cycles, odd $S$-cycles, and long $S$-cycles. We prove a theorem that contains all of these results as well as some new ones.
It turns out that the right objects to study are doubly group-labeled graphs. A doubly group-labeled graph is an oriented graph with edge labels from the direct sum of two abelian groups. A cycle is doubly non-zero, if it is non-zero in both coordinates. We recover all the aforementioned results via an Erd\H os-P\'osa theorem for doubly non-zero cycles. We prove this via a refinement of the Flat Wall Theorem of Robertson and Seymour to doubly group-labeled graphs, which may be of independent interest.
This is joint work with Felix Joos and Paul Wollan.