A unified Erdős-Pósa theorem for cycles in graphs labelled by multiple abelian groups

Area of Science:

• Graph Theory
• Combinatorics
• Discrete Mathematics

Background:

• The Erdős–Pósa theorem established a duality between cycle packing and vertex cover for general cycles.
• This duality does not extend to odd cycles, posing a challenge in graph theory.
• Previous work by Dejter and Neumann-Lara investigated conditions for cycle duality modulo z.

Purpose of the Study:

• To characterize all integer pairs (ℓ, z) for which duality holds for cycles of length ℓ modulo z.
• To generalize this characterization to cycles in graphs labeled with abelian groups.
• To identify obstructions to cycle duality in these generalized settings.

Main Methods:

• Characterization of integer pairs (ℓ, z) for cycle duality.
• Generalization using abelian group labels on graphs.
• Analysis of obstructions to duality.
• Application to graphs embeddable on surfaces.

Main Results:

• Complete characterization of pairs (ℓ, z) admitting cycle duality.
• Extension of duality characterization to graphs with bounded abelian group labels.
• Identification of obstructions, leading to new results and unifying existing ones.
• Analogous characterization for cycles in graphs on fixed compact orientable surfaces.

Conclusions:

• The study provides a comprehensive understanding of cycle duality in graphs.
• It unifies and extends known results concerning cycle packing and vertex cover duality.
• New insights into obstructions and surface embeddings are presented.