A Unified Erds-Posa Theorem for Constrained Cycles

A ((1),(2))-labeled graph is an oriented graph with its edges labeled by elements of the direct sum of two groups (1),(2). A cycle in such a labeled graph is ((1),(2))-non-zero if it is non-zero in both coordinates. Our main result is a generalization of the Flat Wall Theorem of Robertson and Seymour to ((1),(2))-labeled graphs. As an application, we determine all canonical obstructions to the Erds-Posa property for ((1),(2))-non-zero cycles in ((1),(2))-labeled graphs. The obstructions imply that the half-integral Erds-Posa property always holds for ((1),(2))-non-zero cycles.Moreover, our approach gives a unified framework for proving packing results for constrained cycles in graphs. For example, as immediate corollaries we recover the Erds-Posa property for cycles and S-cycles and the half-integral Erds-Posa property for odd cycles and odd S-cycles. Furthermore, we recover Reed's Escher-wall Theorem.We also prove many new packing results as immediate corollaries. For example, we show that the half-integral Erds-Posa property holds for cycles not homologous to zero, odd cycles not homologous to zero, and S-cycles not homologous to zero. Moreover, the (full) Erds-Posa property holds for S-1-S-2-cycles and cycles not homologous to zero on an orientable surface. Finally, we also describe the canonical obstructions to the Erds-Posa property for cycles not homologous to zero and for odd S-cycles.