A unified Erdős-Pósa theorem for constrained cycles - Huynh, Tony; Joos, Felix; Wollan, Paul (Combinatorica, 2019)
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 Erdős-Pósa property for (Γ1,Γ2)-non-zero cycles in (Γ1,Γ2)-labeled graphs. The obstructions imply that the half-integral Erdős-Pósa property always holds for (Γ1,Γ2)-non-zero cycles.
Online first 14 August 2018
Gesehen am 27.07.2022