Jungho Ahn (안정호), A coarse Erdős-Pósa theorem for constrained cycles
2025-02-11 16:30 - 17:30 (Asia/Seoul) | Room B332, IBS (기초과학연구원)
An induced packing of cycles in a graph is a set of vertex-disjoint cycles such that the graph has no edge between distinct cycles of the set. The classic Erdős-Pósa theorem shows that for every positive integer $k$, every graph contains $k$ vertex-disjoint cycles or a set of $O(klog k)$ vertices which intersects every cycle of $G$.
We generalise this classic Erdős-Pósa theorem to induced packings of cycles of length at least $ell$ for any integer $ell$. We show that there exists a function $f(k,ell)=O(ell klog k)$ such that for all positive integers $k$ and $ell$ with $ellgeq3$, every graph $G$ contains an induced packing of $k$ cycles of length at least $ell$ or a set $X$ of at most $f(k,ell)$ vertices such that the closed neighbourhood of $X$ intersects every cycle of $G$.
Furthermore, we extend the result to long cycles containing prescribed vertices. For a graph $G$ and a set $Ssubseteq V(G)$, an $S$-cycle in $G$ is a cycle containing a vertex in $S$. We show that for all positive integers $k$ and $ell$ with $ellgeq3$, every graph $G$, and every set $Ssubseteq V(G)$, $G$ contains an induced packing of $k$ $S$-cycles of length at least $ell$ or a set $X$ of at most $ell k^{O(1)}$ vertices such that the closed neighbourhood of $X$ intersects every cycle of $G$.
Our proofs are constructive and yield polynomial-time algorithms, for fixed $ell$, finding either the induced packing of the constrained cycles or the set $X$.
This is based on joint works with Pascal Gollin, Tony Huynh, and O-joung Kwon.
