Lokshtanov–McCarty bounded-degree region intersection conjecture

Let HH be a graph and let Δ∈N\Delta\in\mathbb{N}. A region intersection graph over a graph H′H' is a graph whose vertices correspond to connected subgraphs of H′H', with two vertices adjacent exactly when the corresponding subgraphs share a vertex.

Lokshtanov–McCarty's conjecture. There exists a graph H′H' such that every HH-induced-minor-free graph with maximum degree at most Δ\Delta is a region intersection graph over an H′H'-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.

References

Primary source

Robert Hickingbotham, “Induced Minors, Asymptotic Dimension, and Baker's Technique”, arXiv:2508.06190 (2025).

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.