Gartland and Lokshtanov's induced-minor-free graph algorithm conjecture

From papers

Let HH be a planar graph. For a fixed integer rr and fixed CMSO2_2 formula ψ\psi, (twr,ψ)(\operatorname{tw} \leq r,\psi)-MWIS is the problem of finding a maximum-weight vertex set inducing a graph of treewidth at most rr that satisfies ψ\psi, or reporting that no such set exists. Also, lcol(3)\operatorname{lcol}(3) denotes the relevant 3-color list-colouring problem. A graph is HH-induced-minor-free if it does not contain HH as an induced minor.

Gartland and Lokshtanov's conjecture. For every fixed rr and CMSO2_2 formula ψ\psi, (twr,ψ)(\operatorname{tw} \leq r,\psi)-MWIS and lcol(3)\operatorname{lcol}(3) can be solved in polynomial time in HH-induced-minor-free graphs.

This conjecture extends polynomial-time algorithmic results from graphs excluding linear forests to induced-minor-free graphs for planar forbidden graphs. Its status is not established in the supplied text.

Progress summary

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

Sources & referencesView supporting material

Primary source

Amir Nikabadi and Paweł Rzążewski, “Induced packing treewidth”, arXiv:2607.07595 (2026).

Solutions 0

No solutions have been posted yet.