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

DOI10.1112/JLMS.12858arXiv2102.01986MaRDI QIDQ6199337FDOQ6199337

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)

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.

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

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

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)

Cites Work

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

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)