A unified half‐integral Erdős–Pósa theorem for cycles in graphs labelled by multiple abelian groups
In: Journal of the London Mathematical Society ; volume 109, issue 1 ; ISSN 0024-6107 1469-7750, 2024
academicJournal
Zugriff:
Erdős and Pósa proved in 1965 that there is a 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 if we restrict to odd cycles. However, in 1999, Reed proved an analogue for odd cycles by relaxing packing to half‐integral packing. We prove a far‐reaching generalisation of the theorem of Reed; if the edges of a graph are labelled by finitely many abelian groups, then there is a duality between the maximum size of a half‐integral packing of cycles whose values avoid a fixed finite set for each abelian group and the minimum size of a vertex set hitting all such cycles. A multitude of natural properties of cycles can be encoded in this setting, for example, cycles of length at least , cycles of length modulo , cycles intersecting a prescribed set of vertices at least times and cycles contained in given ‐homology classes in a graph embedded on a fixed surface. Our main result allows us to prove a duality theorem for cycles satisfying a fixed set of finitely many such properties.
Titel: |
A unified half‐integral Erdős–Pósa theorem for cycles in graphs labelled by multiple abelian groups
|
---|---|
Autor/in / Beteiligte Person: | Gollin, J. Pascal ; Hendrey, Kevin ; Kawarabayashi, Ken‐ichi ; Kwon, O‐joung ; Oum, Sang‐il ; Institute for Basic Science ; National Research Foundation of Korea |
Link: | |
Zeitschrift: | Journal of the London Mathematical Society ; volume 109, issue 1 ; ISSN 0024-6107 1469-7750, 2024 |
Veröffentlichung: | Wiley, 2024 |
Medientyp: | academicJournal |
DOI: | 10.1112/jlms.12858 |
Sonstiges: |
|