BROWSE

Related Scientist

pascalgollin,jochen's photo.

pascalgollin,jochen
이산수학그룹
more info

ITEM VIEW & DOWNLOAD

A unified half-integral Erdős–Pósa theorem for cycles in graphs labelled by multiple abelian groups

Cited 0 time in webofscience Cited 0 time in scopus
42 Viewed 0 Downloaded
Title
A unified half-integral Erdős–Pósa theorem for cycles in graphs labelled by multiple abelian groups
Author(s)
J. Pascal Gollin; Kevin Hendrey; Kawarabayashi, Ken-ichi; O-joung Kwon; Sang-il Oum
Publication Date
2024-01
Journal
Journal of the London Mathematical Society, v.109, no.1
Publisher
Oxford University Press
Abstract
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 (Formula presented.), cycles of length (Formula presented.) modulo (Formula presented.), cycles intersecting a prescribed set of vertices at least (Formula presented.) times and cycles contained in given (Formula presented.) -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. © 2024 The Authors. Journal of the London Mathematical Society is copyright © London Mathematical Society.
URI
https://pr.ibs.re.kr/handle/8788114/15035
DOI
10.1112/jlms.12858
ISSN
0024-6107
Appears in Collections:
Pioneer Research Center for Mathematical and Computational Sciences(수리 및 계산과학 연구단) > Discrete Mathematics Group(이산 수학 그룹) > 1. Journal Papers (저널논문)
Pioneer Research Center for Mathematical and Computational Sciences(수리 및 계산과학 연구단) > 1. Journal Papers (저널논문)
Files in This Item:
There are no files associated with this item.

qrcode

  • facebook

    twitter

  • Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
해당 아이템을 이메일로 공유하기 원하시면 인증을 거치시기 바랍니다.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

Browse