We prove that there exists a function f(k)=O(k^2logk) such that for every C4-free graph G and every k∈ℕ, 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]
On the Erdős-Pósa property for long holes in C_4-free graphs / Huynh, T.; Kwon, O. -J.. - In: SIAM JOURNAL ON DISCRETE MATHEMATICS. - ISSN 0895-4801. - 38:1(2024), pp. 19-42.
On the Erdős-Pósa property for long holes in C_4-free graphs
Huynh, T.;
2024
Abstract
We prove that there exists a function f(k)=O(k^2logk) such that for every C4-free graph G and every k∈ℕ, 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]File allegati a questo prodotto
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
