论文标题
一个由多个阿贝尔组标记的循环的统一的ERDőS-Pósa定理
A unified Erdős-Pósa theorem for cycles in graphs labelled by multiple abelian groups
论文作者
论文摘要
1965年，Erdős和Pósa证明，循环的最大尺寸与顶点组的最小尺寸击中了所有周期之间存在（大约）二元性。这样的二元性不适合奇数周期，Dejter和Neumann Lara在1988年要求整数的所有对$ {（\ ell，Z）} $找到所有对二元性的二元性，这些双重性适用于长度$ \ ell $ modulo $ z $的循环。我们表征了所有这些对，并进一步将这种表征推广到标记有一个有界数的Abelian组的图表中，其值避免了每个组的有界数。这统一了几乎所有已知的循环类型的循环，这些循环承认这是双重性的，并且还提供了新的结果。此外，我们在这种情况下表征了这种二元性的障碍物，从而获得了可在固定紧凑的可定向表面上嵌入的图表中的循环的类似表征。
In 1965, Erdős and Pósa proved that there is an (approximate) duality between the maximum size of a packing of cycles and the minimum size of a vertex set hitting all cycles. Such a duality does not hold for odd cycles, and Dejter and Neumann-Lara asked in 1988 to find all pairs ${(\ell, z)}$ of integers where such a duality holds for the family of cycles of length $\ell$ modulo $z$. We characterise all such pairs, and we further generalise this characterisation to cycles in graphs labelled with a bounded number of abelian groups, whose values avoid a bounded number of elements of each group. This unifies almost all known types of cycles that admit such a duality, and it also provides new results. Moreover, we characterise the obstructions to such a duality in this setting, and thereby obtain an analogous characterisation for cycles in graphs embeddable on a fixed compact orientable surface.
