Bounded-dimension conjecture for fat-minor- and induced-minor-excluding graphs
For every finite graph , the class has bounded asymptotic dimension; that is, there exists such that for every . A weaker conjecture asserts that, for every finite graph , the class likewise has bounded asymptotic dimension.
References
- Asymptotic dimension of graphs excluding an induced or fat minor — arXiv — Robert Hickingbotham, Freddie Illingworth, Piotr Micek, Bartosz Walczak
Source: arXiv
Progress summary
New work proves the conjecture for two broad restricted families, but the general question remains open.
The conjecture asks whether every fixed fat-minor-excluding graph class has bounded asymptotic dimension. The general statement remains open for arbitrary excluded graphs.
Known results
- Every proper minor-closed family has asymptotic dimension at most ; excluding a planar graph as a minor gives at most .
- Hickingbotham’s August 8, 2025 version proves asymptotic dimension at most for hereditary bounded-degree classes excluding a fixed graph as an -fat minor, improving to when the excluded graph is planar.
- The same work proves bounded Baker-treewidth for bounded-degree classes excluding a fixed graph as an induced minor.
October 2026 partial progress
A manuscript by Robert Hickingbotham, Freddie Illingworth, Piotr Micek, and Bartosz Walczak reports the conjectured bounded-dimension property for two further families and consequences for -boundedness and treewidth. It is substantial claimed progress, but does not cover arbitrary graph classes and is unrefereed.
Current status (as of October 2026): The reported restricted cases have claimed proofs, but the general bounded-dimension conjecture remains open and the latest extension is unverified.
Solutions 0
No solutions have been posted yet.