Packing cycles with modularity constraints (Q653988): Difference between revisions

Let \(G\) be a graph and let \(\Gamma\) be an Abelian group with no element of order two. Let \(\gamma:E(G)\to \Gamma\) be a function from the edges of \(G\) to the elements of \(\Gamma\). A non-zero cycle is a cycle \(C\) such that \(\sum_{e\in E(G)}\gamma(e) \not= 0\) where \(0\) is the identity element of \(\Gamma\). Then \(G\) either contains \(k\) vertex disjoint non-zero cycles or there exists a set \(X\subseteq V(G)\) with \(| X| \leq N(k)\) such that \(G-X\) contains no non-zero cycle, where \(N(k)\) is an integer depending on \(k\). An immediate consequence is that for all positive odd integers \(m\), a graph \(G\) either contains \(k\) vertex disjoint cycles of length not congruent to \(0 \mod m\), or there exists a set \(X\) of vertices with \(| X| \leq N(k)\) such that every cycle of \(G-X\) has length congruent to \(0 \mod m\). No such value \(N(k)\) exists when \(m\) is allowed to be even, as examples of \textit{B. Reed} [Combinatorica 19, 267--296 (1999; Zbl 0928.05059)] and \textit{C. Thomassen} [J. Graph Theory 12, 101--111 (1988; Zbl 0662.05032)] show.