DC Field | Value | Language |
---|---|---|
dc.contributor.author | Gollin, J. Pascal | ko |
dc.contributor.author | Hendrey, Kevin | ko |
dc.contributor.author | Kawarabayashi, Ken-ichi | ko |
dc.contributor.author | Kwon, O-joung | ko |
dc.contributor.author | Oum, Sang-il | ko |
dc.date.accessioned | 2024-06-10T02:00:23Z | - |
dc.date.available | 2024-06-10T02:00:23Z | - |
dc.date.created | 2024-06-10 | - |
dc.date.created | 2024-06-10 | - |
dc.date.issued | 2024-01 | - |
dc.identifier.citation | JOURNAL OF THE LONDON MATHEMATICAL SOCIETY-SECOND SERIES, v.109, no.1 | - |
dc.identifier.issn | 0024-6107 | - |
dc.identifier.uri | http://hdl.handle.net/10203/319695 | - |
dc.description.abstract | Erdos and Posa 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 l$\ell$, cycles of length p$p$ modulo q$q$, cycles intersecting a prescribed set of vertices at least t$t$ times and cycles contained in given Z2$\mathbb {Z}_2$-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. | - |
dc.language | English | - |
dc.publisher | WILEY | - |
dc.title | A unified half-integral Erdős-Pósa theorem for cycles in graphs labelled by multiple abelian groups | - |
dc.type | Article | - |
dc.identifier.wosid | 001157209900029 | - |
dc.identifier.scopusid | 2-s2.0-85187572104 | - |
dc.type.rims | ART | - |
dc.citation.volume | 109 | - |
dc.citation.issue | 1 | - |
dc.citation.publicationname | JOURNAL OF THE LONDON MATHEMATICAL SOCIETY-SECOND SERIES | - |
dc.identifier.doi | 10.1112/jlms.12858 | - |
dc.contributor.localauthor | Oum, Sang-il | - |
dc.contributor.nonIdAuthor | Gollin, J. Pascal | - |
dc.contributor.nonIdAuthor | Hendrey, Kevin | - |
dc.contributor.nonIdAuthor | Kawarabayashi, Ken-ichi | - |
dc.contributor.nonIdAuthor | Kwon, O-joung | - |
dc.description.isOpenAccess | N | - |
dc.type.journalArticle | Article | - |
dc.subject.keywordPlus | ERDOS-POSA PROPERTY | - |
dc.subject.keywordPlus | ODD CYCLES | - |
dc.subject.keywordPlus | DISJOINT PATHS | - |
dc.subject.keywordPlus | PACKING | - |
dc.subject.keywordPlus | MINORS | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.