| Naslov: | A unified Erdős–Pósa theorem for cycles in graphs labelled by multiple abelian groups |
|---|
| Avtorji: | ID Gollin, J. Pascal (Avtor)
ID Hendrey, Kevin (Avtor)
ID Kwon, O-joung (Avtor)
ID Oum, Sang-il (Avtor)
ID Yoo, Youngho (Avtor) |
|---|
| Datoteke: |  RAZ_Gollin_J._Pascal_2025.pdf (1,17 MB)
MD5: 5727BF9F169C5746DFD5725EAEABE2E8
 https://link.springer.com/article/10.1007/s00208-025-03293-5
|
|---|
| Jezik: | Angleški jezik |
|---|
| Vrsta gradiva: | Članek v reviji |
|---|
| Tipologija: | 1.01 - Izvirni znanstveni članek |
|---|
| Organizacija: | FAMNIT - Fakulteta za matematiko, naravoslovje in informacijske tehnologije
|
|---|
| Opis: | 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. |
|---|
| Ključne besede: | Erdős-Pósa property, cycle packing, group-labelled graph |
|---|
| Datum objave: | 26.09.2025 |
|---|
| Leto izida: | 2025 |
|---|
| Št. strani: | str. 2507-2559 |
|---|
| Številčenje: | Vol. 393, iss. 2 |
|---|
| PID: | 20.500.12556/RUP-22118  |
|---|
| UDK: | 519.17 |
|---|
| ISSN pri članku: | 0025-5831 |
|---|
| DOI: | 10.1007/s00208-025-03293-5 |
|---|
| COBISS.SI-ID: | 257522179 |
|---|
| Datum objave v RUP: | 17.11.2025 |
|---|
| Število ogledov: | 296 |
|---|
| Število prenosov: | 8 |
|---|
| Metapodatki: |    |
|---|
|
:
|
Kopiraj citat |
|---|
| | | | Skupna ocena: | (0 glasov) |
|---|
| Vaša ocena: | Ocenjevanje je dovoljeno samo prijavljenim uporabnikom. |
|---|
| Objavi na: |  |
|---|
Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše
podrobnosti ali sproži prenos. |
