The Erdős–Pósa parameter conjecture for minor-closed graph classes
The Erdős–Pósa parameter conjecture for minor-closed graph classes
Let 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 , a parameter is bounded in if there is some such that its value is at most on every graph in . Let denote the class of graphs containing as a minor.
Erdős–Pósa parameter conjecture. For every graph , there exists a minor-monotone graph parameter such that has the Erdős–Pósa property in a minor-closed graph class if and only if is bounded in .
For planar , the constant zero function gives such a parameter, but existence for non-planar is not known. The assertion is tied to the open conjecture that graphs are -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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.