The half-integral reduction conjecture for labelled cycles

For an abelian group Γ\Gamma, a subset AΓA\subseteq\Gamma, and a Γ\Gamma-labelled graph (G,γ)(G,\gamma), let OG,γA\mathcal O^A_{G,\gamma} denote the set of cycles whose γ\gamma-values lie in AA. Half-integral reduction conjecture. Let s4s\geq 4 be an integer. If there is a function f ⁣:NNf\colon\mathbb{N}\to\mathbb{N} such that, for every Γ\Gamma-labelled graph (G,γ)(G,\gamma) and every positive integer kk, there are either kk cycles in OG,γA\mathcal O^A_{G,\gamma} such that no vertex belongs to ss of them, or a hitting set for OG,γA\mathcal O^A_{G,\gamma} of size at most f(k)f(k), then there is a function f ⁣:NNf'\colon\mathbb{N}\to\mathbb{N} such that, for every Γ\Gamma-labelled graph (G,γ)(G',\gamma') and every positive integer kk, there are either kk cycles in OG,γA\mathcal O^A_{G',\gamma'} such that no vertex belongs to three of them, or a hitting set for OG,γA\mathcal O^A_{G',\gamma'} of size at most f(k)f'(k). This proposes that an Erdős–Pósa property with bounded vertex overlap s4s\geq4 implies its half-integral analogue with overlap three for cycles whose group values lie in AA; the supplied text gives no resolution.

Sources & referencesView supporting material

Primary source

J. Pascal Gollin, Kevin Hendrey, O-joung Kwon, Sang-il Oum and Youngho Yoo, “A unified Erdős-Pósa theorem for cycles in graphs labelled by multiple abelian groups”, arXiv:2209.09488 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.