Lokshtanov–McCarty bounded-degree region intersection conjecture

From papers

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

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

No solutions have been posted yet.