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

Less than 1 year old · traced to

Let FF be a forest and let R⊆V(F)R \subseteq V(F). For a graph GG, a set S⊆V(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 X⊆V(G)X \subseteq V(G) with
∣X∣≤∣V(F)∣(k−1)|X| \leq |V(F)|(k-1)

such that there is no model of (F,R)(F,R) in (G−X,S∖X)(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.

References

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).

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.