← All problems

Bounded-dimension conjecture for fat-minor- and induced-minor-excluding graphs

For every finite graph HH, the class CHfat={G:H is not a fat minor of G}\mathcal{C}^{\mathrm{fat}}_H=\{G: H\text{ is not a fat minor of }G\} has bounded asymptotic dimension; that is, there exists dH∈Nd_H\in\mathbb{N} such that asdim⁡(G)≤dH\operatorname{asdim}(G)\le d_H for every G∈CHfatG\in\mathcal{C}^{\mathrm{fat}}_H. A weaker conjecture asserts that, for every finite graph HH, the class CHind={G:H is not an induced minor of G}\mathcal{C}^{\mathrm{ind}}_H=\{G: H\text{ is not an induced minor of }G\} likewise has bounded asymptotic dimension.

References

Source: arXiv

Progress summary

Refreshed
Open · progress reported

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 22; excluding a planar graph as a minor gives at most 11.
  • Hickingbotham’s August 8, 2025 version proves asymptotic dimension at most 22 for hereditary bounded-degree classes excluding a fixed graph as an rr-fat minor, improving to 11 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 χ\chi-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.

Sources

Solutions 0

No solutions have been posted yet.