| Title: | A unified Erdős–Pósa theorem for cycles in graphs labelled by multiple abelian groups |
|---|
| Authors: | ID Gollin, J. Pascal (Author)
ID Hendrey, Kevin (Author)
ID Kwon, O-joung (Author)
ID Oum, Sang-il (Author)
ID Yoo, Youngho (Author) |
|---|
| Files: |  RAZ_Gollin_J._Pascal_2025.pdf (1,17 MB)
MD5: 5727BF9F169C5746DFD5725EAEABE2E8
 https://link.springer.com/article/10.1007/s00208-025-03293-5
|
|---|
| Language: | English |
|---|
| Work type: | Article |
|---|
| Typology: | 1.01 - Original Scientific Article |
|---|
| Organization: | FAMNIT - Faculty of Mathematics, Science and Information Technologies
|
|---|
| Abstract: | 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 (l, z) of integers where such a duality holds for the family of cycles of length l 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. |
|---|
| Keywords: | Erdős-Pósa property, cycle packing, group-labelled graph |
|---|
| Publication date: | 26.09.2025 |
|---|
| Year of publishing: | 2025 |
|---|
| Number of pages: | str. 2507-2559 |
|---|
| Numbering: | Vol. 393, iss. 2 |
|---|
| PID: | 20.500.12556/RUP-22118  |
|---|
| UDC: | 519.17 |
|---|
| ISSN on article: | 0025-5831 |
|---|
| DOI: | 10.1007/s00208-025-03293-5 |
|---|
| COBISS.SI-ID: | 257522179 |
|---|
| Publication date in RUP: | 17.11.2025 |
|---|
| Views: | 304 |
|---|
| Downloads: | 8 |
|---|
| Metadata: |    |
|---|
|
:
|
Copy citation |
|---|
| | | | Average score: | (0 votes) |
|---|
| Your score: | Voting is allowed only for logged in users. |
|---|
| Share: |  |
|---|
Hover the mouse pointer over a document title to show the abstract or click
on the title to get all document metadata. |
