Erdős–Pósa Properties of Induced Subdivisions

Definitions and mathematical statement

Use the following conventional formulation, subject to the qualifications below. All graphs are finite, undirected, and simple. A subdivision of a graph $H$ is obtained by replacing each edge $uv\in E(H)$ by a $u$--$v$ path of positive length, with all replacement paths internally vertex-disjoint and with no internal vertex belonging to $V(H)$. An induced $H$-subdivision in a graph $G$ is an induced subgraph $G[X]$ isomorphic to a subdivision of $H$.

A class $\mathcal C$ of graphs has the vertex Erdős--Pósa property if there exists a function \[ f_{\mathcal C}\colon {\mathbb{Z}}_{\geq 1}\longrightarrow {\mathbb{Z}}_{\geq 0} \] such that, for every graph $G$ and every integer $k\geq 1$, at least one of the following holds:

1. There exist pairwise disjoint sets $X_1,\ldots,X_k\subseteq V(G)$ such that $G[X_i]\in\mathcal C$ for every $i$.
2. There exists $S\subseteq V(G)$ with $|S|\leq f_{\mathcal C}(k)$ such that $G-S$ contains no induced subgraph belonging to $\mathcal C$.

For a fixed graph $H$, let $\mathcal S_H$ be the class of all subdivisions of $H$. The main question is to characterize the graphs $H$ for which $\mathcal S_H$ has this property. The function may depend on $H$, but must be independent of $G$.

The supplied record singles out $H=K_4$, the complete graph on four vertices, and a fan whose path has length $3$. Under the usual fan and path-length conventions, the latter graph has vertices $a,v_0,v_1,v_2,v_3$ and exactly the edges \[ \{v_0v_1,v_1v_2,v_2v_3\}\cup\{av_i:0\leq i\leq 3\}. \] It asks whether each of these two classes $\mathcal S_H$ has the property.

A further singled-out question concerns induced even cycles. Interpreted as even holes, this asks whether the class \[ \mathcal E=\{C_{2r}:r\geq 2\} \] has the same property, where $C_m$ is the cycle on $m$ vertices and occurrences in $G$ must be induced. This parity-restricted question is distinct from the question for subdivisions of a fixed even cycle: unrestricted subdivision does not preserve even length.

The source does not explicitly specify finite simple graphs, the vertex rather than edge version of the property, or the fan convention. These conventions therefore require source review. The interpretation of the even-cycle subquestion as even holes also requires confirmation from the report. The supplied open status and verification label are registry annotations, not independent mathematical verification.

Short English statement

Characterize the graphs $H$ for which every graph either contains $k$ vertex-disjoint induced subdivisions of $H$, or has a vertex set of size bounded only by $H$ and $k$ meeting every such subdivision. The record highlights $K_4$, a fan over a path of three edges, and a separate question about induced even cycles. The stated conventions and interpretations require human mathematical review.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $30004034$, source problem code catalogue entry, title Erdős--Pósa Properties of Induced Subdivisions, in the Oberwolfach Reports Open Problems collection. No individual proposer is supplied; the recorded proposed year is 2019.
• Supplied report citation: Graph Theory (2020), Oberwolfach Reports, pp. 5--63, DOI 10.4171/owr/2019/1. https://doi.org/10.4171/owr/2019/1. The citation's 2020 label and the record's 2019 year are retained as supplied; their relationship has not been checked.
• Supplied literature reference: Kim and Kwon, Journal of Combinatorial Theory B. https://doi.org/10.1016/j.jctb.2020.05.002.
• Supplied literature reference: On the Erdos--Posa property for long holes. https://epubs.siam.org/doi/pdf/10.1137/21M1435239?download=true.
• Literature assessment dated exactly 2026-08-22: the supplied curation states that ordinary holes have the Erdős--Pósa property, holes of length at least five do not, and the report's induced even-cycle subquestion remains unresolved. This is supplied dated curation derived from the OWR record, not an independently verified assessment. The record requests independent verification of time-sensitive status and cited claims.
• The registry labels the problem open and the statement corrected_verified. Its verification note says that mathematical content was preserved while notation, typography, duplicate clauses, or omitted definitions were repaired for self-contained publication. These are supplied provenance claims; no source was visited or independently checked for this draft.