Packing cycles with modularity constraints
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.
- Packing cycles in undirected group-labelled graphs
- Packing cycles through prescribed vertices under modularity constraints
- Non-zero disjoint cycles in highly connected group labelled graphs
- scientific article; zbMATH DE number 617590
- On the size of graphs whose cycles have length divisible by a fixed integer
- Covering Theorems for Ordered Sets
- Disjoint A-paths in digraphs
- Graph minors. X: Obstructions to tree-decomposition
- Highly parity linked graphs
- scientific article; zbMATH DE number 3019031 (Why is no real title available?)
- Mangoes and blueberries
- Maximum-Minimum Sätze und verallgemeinerte Faktoren von Graphen
- Non-zero disjoint cycles in highly connected group labelled graphs
- On the presence of disjoint subgraphs of a specified type
- Packing non-zero A-paths in an undirected model of group labeled graphs
- Packing non-zero \(A\)-paths in group-labelled graphs
- Quickly excluding a planar graph
- The Erdős-Pósa property for odd cycles in graphs of large connectivity
- The Erdős-Pósa property for odd cycles in highly connected graphs
- The Erdős-Pósa property for vertex- and edge-disjoint odd cycles in graphs on orientable surfaces
- Über die Maximalzahl kreuzungsfreier H-Wege
- \(K_4\)-expansions have the edge-Erdős-Pósa property
- Packing \(A\)-paths of length zero modulo four
- Half-integral packing of odd cycles through prescribed vertices
- Recent techniques and results on the Erdős-Pósa property
- Non-zero disjoint cycles in highly connected group labelled graphs
- A faster parameterized algorithm for Group Feedback Edge Set
- Packing cycles through prescribed vertices under modularity constraints
- Frames, \(A\)-paths, and the Erdős-Pósa property
- Erdős-Pósa property for labeled minors: 2-connected minors
- Erdős-Pósa property and its algorithmic applications: parity constraints, subset feedback set, and subset packing
- \(K_4\)-subdivisions have the edge-Erdős-Pósa property
- Packing cycles in undirected group-labelled graphs
- A unified half‐integral Erdős–Pósa theorem for cycles in graphs labelled by multiple abelian groups
- A unified Erdős-Pósa theorem for cycles in graphs labelled by multiple abelian groups
- Finding a shortest non-zero path in group-labeled graphs
- Group vertex-arboricity of group-labelled graphs
- Towards the proximity conjecture on group-labeled matroids
This page was built for publication: Packing cycles with modularity constraints
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q653988)
