Georgakopoulos coarse grid minor conjecture

About 1 year old · traced to

Let HH be a planar graph. A graph is HH-induced-minor-free if it does not contain HH as an induced minor, and a graph is qq-quasi-isometric to a graph of treewidth at most kk if such a quasi-isometry exists with parameter qq.

Georgakopoulos's coarse grid minor conjecture. For every planar graph HH, there exist k,q∈Nk,q\in\mathbb{N} such that every HH-induced-minor-free graph is qq-quasi-isometric to a graph with treewidth at most kk.

The conjecture is a coarse analogue of the grid-minor obstruction principle and is described as a major open problem in coarse graph theory. The paper notes that the original formulation uses forbidden fat-minors, which is more general than forbidden induced minors.

References

Primary source

Maria Chudnovsky and Robert Hickingbotham, “Coarse Balanced Separators and Tree-Decompositions”, arXiv:2505.06550 (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.