Functional monotonicity conjecture for contraction distance to minor-closed classes
Functional monotonicity conjecture for contraction distance to minor-closed classes
Let be a minor-closed graph class. For a graph , let denote the minimum number of edge identifications needed to transform into a graph in , and let denote the minimum number of edge contractions needed to transform into a graph in . Functional monotonicity conjecture. There is a function such that for every graph ,
This would extend the displayed polynomial relationship proved in the paper for forests to every minor-closed class, showing that edge-contraction distance is bounded as a function of edge-identification distance; no resolution is given.
Sources & referencesView supporting material
Primary source
Laure Morelle, Ignasi Sau and Dimitrios M. Thilikos, “Vertex identification to a forest”, arXiv:2409.08883 (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.