On the Erdős-Pósa property for long holes in $C_4$-free graphs

Abstract

We prove that there exists a function $f(k)=\mathcal{O}(k^2\log k)$ such that for every $C_4$-free graph $G$ and every $k\in \mathbb{N}$, $G$ either contains $k$ vertex-disjoint holes of length at least $6$, or a set $X$ of at most $f(k)$ vertices such that $G-X$ has no hole of length at least $6$. This answers a question of Kim and Kwon [Erdős-Pósa property of chordless cycles and its applications. JCTB 2020].

19 pages, 5 figures