Linear Erdős–Pósa bound for models of forests

From papers

Let FF be a forest and let RV(F)R \subseteq V(F). For a graph GG, a set SV(G)S \subseteq V(G), and a positive integer kk, consider models of (F,R)(F,R) in (G,S)(G,S).

Linear Erdős–Pósa conjecture. At least one of the following holds:

  1. There are kk pairwise vertex-disjoint models of (F,R)(F,R) in (G,S)(G,S).
  2. There is a set XV(G)X \subseteq V(G) with
XV(F)(k1)|X| \leq |V(F)|(k-1)

such that there is no model of (F,R)(F,R) in (GX,SX)(G-X,S \setminus X).

This would give a bound linear in the size of the forest, improving the dependence on V(T)|V(T)| in the established Erdős–Pósa result for SS-rooted models of a fixed tree. The conjecture is stated in the more general setting of (F,R)(F,R)-models and is open in the supplied source.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Quentin Claus, Gwenaël Joret, Clément Rambaud and Eileen Robinson, “Erdős-Pósa property of rooted tree minors”, arXiv:2607.26638 (2026).

Solutions 0

No solutions have been posted yet.