Back to Search
Start Over
Packing cycles in undirected group-labelled graphs
- Source :
- J. Combin. Theory Ser. B 161 (2023), 228-267
- Publication Year :
- 2020
-
Abstract
- We prove a refinement of the flat wall theorem of Robertson and Seymour to undirected group-labelled graphs $(G,\gamma)$ where $\gamma$ assigns to each edge of an undirected graph $G$ an element of an abelian group $\Gamma$. As a consequence, we prove that $\Gamma$-nonzero cycles (cycles whose edges sum to a non-identity element of $\Gamma$) satisfy the half-integral Erd\H{o}s-P\'osa property, and we also recover a result of Wollan that, if $\Gamma$ has no element of order two, then $\Gamma$-nonzero cycles satisfy the Erd\H{o}s-P\'osa property. As another application, we prove that if $m$ is an odd prime power, then cycles of length $\ell \mod m$ satisfy the Erd\H{o}s-P\'osa property for all integers $\ell$. This partially answers a question of Dejter and Neumann-Lara from 1987 on characterizing all such integer pairs $(\ell,m)$.
- Subjects :
- Mathematics - Combinatorics
Subjects
Details
- Database :
- arXiv
- Journal :
- J. Combin. Theory Ser. B 161 (2023), 228-267
- Publication Type :
- Report
- Accession number :
- edsarx.2009.11266
- Document Type :
- Working Paper
- Full Text :
- https://doi.org/10.1016/j.jctb.2023.02.011