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.
References
Primary source
Amir Nikabadi and Paweł Rzążewski, “Induced packing treewidth”, arXiv:2607.07595 (2026).
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
No solutions have been posted yet.