Functional monotonicity conjecture for contraction distance to minor-closed classes

Let H\mathcal{H} be a minor-closed graph class. For a graph GG, let idH(G)\mathsf{id}_{\mathcal{H}}(G) denote the minimum number of edge identifications needed to transform GG into a graph in H\mathcal{H}, and let ecH(G)\mathsf{ec}_{\mathcal{H}}(G) denote the minimum number of edge contractions needed to transform GG into a graph in H\mathcal{H}. Functional monotonicity conjecture. There is a function fH:NNf_{\mathcal{H}}:\mathbb{N}\to\mathbb{N} such that for every graph GG,

ecH(G)fH(idH(G)).\mathsf{ec}_{\mathcal{H}}(G)\leq f_{\mathcal{H}}(\mathsf{id}_{\mathcal{H}}(G)).

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

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.