The Erdős–Pósa parameter conjecture for minor-closed graph classes

Let HH be a graph. A graph class is minor-closed if it contains every minor of each of its graphs. A graph parameter is minor-monotone if its value does not increase when taking a minor. For a graph class G\mathcal{G}, a parameter is bounded in G\mathcal{G} if there is some coindentinNc oindentin\mathbb{N} such that its value is at most cc on every graph in G\mathcal{G}. Let MH\mathcal{M}_H denote the class of graphs containing HH as a minor.

Erdős–Pósa parameter conjecture. For every graph HH, there exists a minor-monotone graph parameter EPH\text{\scriptsize\textsf{EP}}_H such that MH\mathcal{M}_H has the Erdős–Pósa property in a minor-closed graph class G\mathcal{G} if and only if EPH\text{\scriptsize\textsf{EP}}_H is bounded in G\mathcal{G}.

For planar HH, the constant zero function gives such a parameter, but existence for non-planar HH is not known. The assertion is tied to the open conjecture that graphs are ω2\omega^2-well-quasi-ordered by minors, and a constructive or canonical description of the parameter would have algorithmic significance.

Sources & referencesView supporting material

Primary source

Christophe Paul, Evangelos Protopapas, Dimitrios M. Thilikos and Sebastian Wiederrecht, “Delineating Half-Integrality of the Erdős-Pósa Property for Minors: the Case of Surfaces”, arXiv:2406.16647 (2024).

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.