ON THE ERDŐS-PÓSA PROPERTY FOR LONG HOLES IN C4-FREE GRAPHS

Abstract

We prove that there exists a function f(k) = Ϭ(k2 log k) such that for every C4-free graph G and every k Є \BbbN, G contains either 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 [J. Combin. Theory Ser. B, 145 (2020), pp. 65-112]. © 2024 Society for Industrial and Applied Mathematics Publications. All rights reserved.