Gartland and Lokshtanov's induced-minor-free graph algorithm conjecture
Gartland and Lokshtanov's induced-minor-free graph algorithm conjecture
Let be a planar graph. For a fixed integer and fixed CMSO formula , -MWIS is the problem of finding a maximum-weight vertex set inducing a graph of treewidth at most that satisfies , or reporting that no such set exists. Also, denotes the relevant 3-color list-colouring problem. A graph is -induced-minor-free if it does not contain as an induced minor.
Gartland and Lokshtanov's conjecture. For every fixed and CMSO formula , -MWIS and can be solved in polynomial time in -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
Sign in to submit a solution.
No solutions have been posted yet.