Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2020
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2009.11266 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
Tabla de Contenidos:
- We prove a refinement of the flat wall theorem of Robertson and Seymour to undirected group-labelled graphs $(G,γ)$ where $γ$ assigns to each edge of an undirected graph $G$ an element of an abelian group $Γ$. As a consequence, we prove that $Γ$-nonzero cycles (cycles whose edges sum to a non-identity element of $Γ$) satisfy the half-integral Erdős-Pósa property, and we also recover a result of Wollan that, if $Γ$ has no element of order two, then $Γ$-nonzero cycles satisfy the Erdős-Pósa property. As another application, we prove that if $m$ is an odd prime power, then cycles of length $\ell \mod m$ satisfy the Erdős-Pósa 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)$.