Strong transversal property forest characterization

Informal: characterization of graphs with the strong transversal property · arXiv:2111.00532

arXiv Informal medium confidence— first stated 2024-02-06

Authors: Alex Scott, Paul Seymour, Sophie Spirkl

Status open high confidence

The question of which graphs H have the strong transversal property — i.e., for which H there exists epsilon > 0 guaranteeing a B-transversal copy of H in every graph with an (epsilon W, epsilon W)-cohesive blockade of local degree less than epsilon W — is posed as an open problem in Section 2 of the source paper. The paper establishes that H must be a forest, proves the property for paths and certain caterpillar-like trees, and shows it fails for trees containing a vertex of degree d with 2^{d-1} >= |H|. No complete characterization has been found, and no follow-up paper resolving or substantially extending this question was found in five targeted web searches covering arXiv and the published literature through May 2026.

Reviewer notes. Two superficially related arXiv papers were checked: arXiv:2305.05713 studies density thresholds for connected/Hamiltonian transversals in multipartite graphs (a different setting, not blockades/local-degree conditions), and arXiv:2310.06354 studies rainbow transversals in families of trees — neither addresses the strong transversal property as defined in 2111.00532. The source paper was published in SIAM J. Discrete Math. 38(1), 2024, pp. 645–667. No follow-up found.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Informal. Which graphs $H$ have the strong transversal property, i.e., for which $H$ does there exist $\varepsilon > 0$ such that every graph $G$ with an $(\varepsilon W, \varepsilon W)$-cohesive blockade $\mathcal{B} = (B_1, \ldots, B_{|H|})$ of local degree less than $\varepsilon W$ contain a $\mathcal{B}$-transversal copy of $H$?

Context

The question opens Section 2. The authors note that $H$ must be a forest, and give partial results in Theorem 2.1: paths have the property; certain caterpillar-like trees do; trees with a vertex of degree $d$ satisfying $2^{d-1} \geq |H|$ do not. No complete characterization is given, and the converse of the component-wise criterion fails.

Notes. Posed as a driving question for Section 2 without a formal label or environment.

Source paper

Pure pairs. IX. Transversal trees
Alex Scott, Paul Seymour, Sophie Spirkl · 2024-02-06
https://arxiv.org/abs/2111.00532 PDF source