Packing and covering induced subdivisions

DOI10.1137/18M1226166MaRDI QIDQ4986803zbMATH OpenFDO

Authors O-joung Kwon, Jean-Florent Raymond

Publication date 28 April 2021

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

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

zbMATH Keywords

Erdős-Pósa propertyinduced subdivisionpacking and covering

Mathematics Subject Classification ID

Paths and cycles (05C38) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: A class $mathcalF$ of graphs has the induced ErdH{o}s-P'osa property if there exists a function $f$ such that for every graph $G$ and every positive integer $k$, $G$ contains either $k$ pairwise vertex-disjoint induced subgraphs that belong to $mathcalF$, or a vertex set of size at most $f(k)$ hitting all induced copies of graphs in $mathcalF$. Kim and Kwon (SODA'18) showed that for a cycle $C_{ell}$ of length $ell$, the class of $C_{ell}$-subdivisions has the induced ErdH{o}s-P'osa property if and only if $ellle4$. In this paper, we investigate whether or not the class of $H$-subdivisions has the induced ErdH{o}s-P'osa property for other graphs $H$. We completely settle the case when $H$ is a forest or a complete bipartite graph. Regarding the general case, we identify necessary conditions on $H$ for the class of $H$-subdivisions to have the induced ErdH{o}s-P'osa property. For this, we provide three basic constructions that are useful to prove that the class of the subdivisions of a graph does not have the induced ErdH{o}s-P'osa property. Among remaining graphs, we prove that if $H$ is either the diamond, the $1$-pan, or the $2$-pan, then the class of $H$-subdivisions has the induced ErdH{o}s-P'osa property.

Recommendations

• \(K_4\)-subdivisions have the edge-Erdős-Pósa property
• On the presence of disjoint subgraphs of a specified type
• Induced subdivisions and bounded expansion
• Strengthening Erdős -- Pósa property for minor-closed graph classes
• Pure pairs. II: Excluding all subdivisions of a graph

Cites work

• \(K_4\)-expansions have the edge-Erdős-Pósa property
• 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 tighter Erdős-Pósa function for long cycles
• Additivity of the genus of a graph
• An \(O(\log \mathrm{OPT})\)-approximation for covering and packing minor models of \(\theta _r\)
• Approximation and kernelization for chordal vertex deletion
• Erdős-Pósa property of chordless cycles and its applications
• Existence and explicit constructions of \(q+1\) regular Ramanujan graphs for every prime power \(q\)
• Frames, \(A\)-paths, and the Erdős-Pósa property
• Graph minors. V. Excluding a planar graph
• Graph theory
• Graphs on surfaces
• Hitting forbidden minors: approximation and kernelization
• scientific article; zbMATH DE number 1057879 (Why is no real title available?)
• scientific article; zbMATH DE number 3215864 (Why is no real title available?)
• In absence of long chordless cycles, large tree-width becomes a local phenomenon
• Maximum-Minimum Sätze und verallgemeinerte Faktoren von Graphen
• New spectral lower bounds on the bisection width of graphs
• On the presence of disjoint subgraphs of a specified type
• Recent techniques and results on the Erdős-Pósa property
• The Erdős-Pósa property for long circuits

Cited in

(5)

• Induced subdivisions and bounded expansion
• \(K_4\)-subdivisions have the edge-Erdős-Pósa property
• Covering and packing of rectilinear subdivision
• On the Erdős–Pósa Property for Long Holes in \(\boldsymbol{C_4}\)-Free Graphs
• Induced subdivisions with pinned branch vertices

This page was built for publication: Packing and covering induced subdivisions

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