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]
2024
graph theory, induced subgraphs, holes, packing, covering
01 Pubblicazione su rivista::01a Articolo in rivista
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.
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1707388
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact