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

DOI10.1112/JLMS.12858MaRDI QIDQ6199337zbMATH OpenFDO

Authors J. Pascal Gollin, Kevin Hendrey, Ken-ichi Kawarabayashi, O-joung Kwon, Sang-Il Oum

Publication date 23 February 2024

Published in Journal of the London Mathematical Society (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2102.01986

zbMATH Keywords

duality theorem for cycles

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Abstract: ErdH{o}s and P'{o}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 $ell$, cycles of length $p$ modulo $q$, cycles intersecting a prescribed set of vertices at least $t$ times, and cycles contained in given $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.

Recommendations

• Packing cycles in undirected group-labelled graphs
• A unified Erdős-Pósa theorem for constrained cycles
• Half-integral packing of odd cycles through prescribed vertices
• Packing cycles through prescribed vertices under modularity constraints

Cites work

• scientific article; zbMATH DE number 4156480 (Why is no real title available?)
• scientific article; zbMATH DE number 2103273 (Why is no real title available?)
• A unified Erdős-Pósa theorem for constrained cycles
• Any 𝑛 arithmetic progressions covering the first 2ⁿ integers cover all integers
• Covering intervals with arithmetic progressions
• Excluding a group-labelled graph
• Frames, \(A\)-paths, and the Erdős-Pósa property
• Graph minors. V. Excluding a planar graph
• Graph minors. VII: Disjoint paths on a surface
• Graph minors. X: Obstructions to tree-decomposition
• Graph minors. XIII: The disjoint paths problem
• Graph theory
• Graphs on surfaces
• Half-integral packing of odd cycles through prescribed vertices
• Highly parity linked graphs
• Mangoes and blueberries
• On Independent Circuits Contained in a Graph
• On the presence of disjoint subgraphs of a specified type
• Packing \(A\)-paths of length zero modulo a prime
• Packing cycles in undirected group-labelled graphs
• Packing cycles with modularity constraints
• Packing directed circuits
• Packing non-zero \(A\)-paths in an undirected model of group labeled graphs
• Packing topological minors half‐integrally
• Parity Linkage and the Erdős–Pósa Property of Odd Cycles through Prescribed Vertices in Highly Connected Graphs
• Quickly excluding a planar graph
• Representing Homology Classes on Surfaces
• The Erdős-Pósa property for odd cycles in graphs of large connectivity
• The Erdős-Pósa property for odd cycles in highly connected graphs

This page was built for publication: A unified half‐integral Erdős–Pósa theorem for cycles in graphs labelled by multiple abelian groups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6199337)