The Half-integral Erdös-Pósa Property for Non-null Cycles

Abstract

A Group Labeled Graph is a pair $(G,\Lambda )$ where $G$ is an oriented graph and $\Lambda$ is a mapping from the arcs of $G$ to elements of a group. A (not necessarily directed) cycle $C$ is called non-null if for any cyclic ordering of the arcs in $C$, the group element obtained by `adding' the labels on forward arcs and `subtracting' the labels on reverse arcs is not the identity element of the group. Non-null cycles in group labeled graphs generalize several well-known graph structures, including odd cycles. In this paper, we prove that non-null cycles on Group Labeled Graphs have the half-integral Erdös-Pósa property. That is, there is a function $f:\mathbb{N}\to \mathbb{N}$ such that for any $k\in \mathbb{N}$, any group labeled graph $(G,\Lambda )$ has a set of $k$ non-null cycles such that each vertex of $G$ appears in at most two of these cycles or there is a set of at most $f(k)$ vertices that intersects every non-null cycle. Since it is known that non-null cycles do not have the integeral Erdös-Pósa property in general, a half-integral Erdös-Pósa result is the best one could hope for.