On the Erdős–Pósa Property for Long Holes in C₄-Free Graphs

DOI10.1137/21M1435239MaRDI QIDQ6146268zbMATH OpenOpenAlexFDO

Authors

Publication date 10 January 2024

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2105.11799

zbMATH Keywords

chordal graphsErdős-Pósa propertyholes

Mathematics Subject Classification ID

Distance in graphs (05C12) Paths and cycles (05C38) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Structural characterization of families of graphs (05C75)

Abstract: We prove that there exists a function $f(k)=mathcalO(k^{2}logk)$ such that for every $C_4$-free graph $G$ and every $kinmathbbN$, $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 [ErdH{o}s-P'osa property of chordless cycles and its applications. JCTB 2020].

Recommendations

• A tight Erdős-Pósa function for long cycles
• The Erdős-Hajnal conjecture for long holes and antiholes
• A tighter Erdős-Pósa function for long cycles
• Large cliques in \(C_4\)-free graphs
• The Erdős-Pósa property for long circuits

Cites work

• A new proof and generalizations of a theorem of Erdős and Pósa on graphs withoutk+1 independent circuits
• A tight Erdős-Pósa function for long cycles
• A tight Erdős-Pósa function for planar minors
• A tighter Erdős-Pósa function for long cycles
• A unified Erdős-Pósa theorem for constrained cycles
• A variation of Menger's theorem for long paths
• Approximation and kernelization for chordal vertex deletion
• Erdős-Pósa property of chordless cycles and its applications
• Graph theory
• scientific article; zbMATH DE number 4156480 (Why is no real title available?)
• Long cycles through prescribed vertices have the Erdős-Pósa property
• Mangoes and blueberries
• On Independent Circuits Contained in a Graph
• Packing and covering induced subdivisions
• Packing cycles through prescribed vertices
• Recent techniques and results on the Erdős-Pósa property
• The Erdős-Pósa property for long circuits

This page was built for publication: On the Erdős–Pósa Property for Long Holes in \(\boldsymbol{C_4}\)-Free Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6146268)