Lokshtanov–McCarty bounded-degree region intersection conjecture
Lokshtanov–McCarty bounded-degree region intersection conjecture
Let be a graph and let . A region intersection graph over a graph is a graph whose vertices correspond to connected subgraphs of , with two vertices adjacent exactly when the corresponding subgraphs share a vertex.
Lokshtanov–McCarty's conjecture. There exists a graph such that every -induced-minor-free graph with maximum degree at most is a region intersection graph over an -minor-free graph.
This is the bounded-degree version of a conjecture independently attributed to Lokshtanov and McCarty. The unrestricted conjecture was recently disproved, while the bounded-degree version is proposed in the source as an open revival.
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
Robert Hickingbotham, “Induced Minors, Asymptotic Dimension, and Baker's Technique”, arXiv:2508.06190 (2025).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.