Erdős and Pósa proved in 1965 that there is a duality between the maximum size of a packing of cycles and the minimum size of a vertex set hitting all cycles. We therefore say that cycles satisfy the Erdős-Pósa property. However, while odd cycles do not satisfy the Erdős-Pósa property, Reed proved in 1999 an analogue by relaxing packing to half-integral packing, where each vertex is allowed to be contained in at most two such cycles. Moreover, he gave a structural characterisation for when the Erdős-Pósa property for odd cycles fails.
We prove a far-reaching generalisation of the theorem of Reed; if the edges of a graph are labelled by finitely many abelian groups, then the cycles whose values avoid a fixed finite set for each abelian group satisfy the half-integral Erdős-Pósa property, and we similarly give a structural characterisation for the failure of the Erdős-Pósa property.
A multitude of natural properties of cycles can be encoded in this setting. For example, we show that the cycles of length $\ell$ modulo $m$ satisfy the half-integral Erdős-Pósa property, and we characterise for which values of $\ell$ and $m$ these cycles satisfy the Erdős-Pósa property.
This is joint work with Kevin Hendrey, Ken-ichi Kawarabayashi, O-joung Kwon, Sang-il Oum, and Youngho Yoo.
|
