A unified Erdős-Pósa theorem for cycles in graphs labelled by multiple abelian groups
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2022
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866908765592223744 |
|---|---|
| author | Gollin, J. Pascal Hendrey, Kevin Kwon, O-joung Oum, Sang-il Yoo, Youngho |
| author_facet | Gollin, J. Pascal Hendrey, Kevin Kwon, O-joung Oum, Sang-il Yoo, Youngho |
| contents | In 1965, Erdős and Pósa proved that there is an (approximate) duality between the maximum size of a packing of cycles and the minimum size of a vertex set hitting all cycles. Such a duality does not hold for odd cycles, and Dejter and Neumann-Lara asked in 1988 to find all pairs ${(\ell, z)}$ of integers where such a duality holds for the family of cycles of length $\ell$ modulo $z$. We characterise all such pairs, and we further generalise this characterisation to cycles in graphs labelled with a bounded number of abelian groups, whose values avoid a bounded number of elements of each group. This unifies almost all known types of cycles that admit such a duality, and it also provides new results. Moreover, we characterise the obstructions to such a duality in this setting, and thereby obtain an analogous characterisation for cycles in graphs embeddable on a fixed compact orientable surface. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2209_09488 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | A unified Erdős-Pósa theorem for cycles in graphs labelled by multiple abelian groups Gollin, J. Pascal Hendrey, Kevin Kwon, O-joung Oum, Sang-il Yoo, Youngho Combinatorics 05C38, 05C70, 05C78, 05C25 In 1965, Erdős and Pósa proved that there is an (approximate) duality between the maximum size of a packing of cycles and the minimum size of a vertex set hitting all cycles. Such a duality does not hold for odd cycles, and Dejter and Neumann-Lara asked in 1988 to find all pairs ${(\ell, z)}$ of integers where such a duality holds for the family of cycles of length $\ell$ modulo $z$. We characterise all such pairs, and we further generalise this characterisation to cycles in graphs labelled with a bounded number of abelian groups, whose values avoid a bounded number of elements of each group. This unifies almost all known types of cycles that admit such a duality, and it also provides new results. Moreover, we characterise the obstructions to such a duality in this setting, and thereby obtain an analogous characterisation for cycles in graphs embeddable on a fixed compact orientable surface. |
| title | A unified Erdős-Pósa theorem for cycles in graphs labelled by multiple abelian groups |
| topic | Combinatorics 05C38, 05C70, 05C78, 05C25 |
| url | https://arxiv.org/abs/2209.09488 |