Asymptotic dimension of graphs excluding an induced or fat minor

Abstract

Asymptotic dimension is a large-scale invariant of metric spaces that was introduced by Gromov (1993). A major open problem in coarse graph theory asks whether, for every fixed graph H, the class of graphs excluding H as a fat minor has bounded asymptotic dimension. A weaker conjecture asserts the same conclusion for graphs excluding H as an induced minor. We substantially expand the range of graphs H for which these conjectures are known to hold. Specifically, we prove bounded asymptotic dimension for the following classes of graphs: graphs excluding a fixed planar graph as a fat minor; and graphs excluding a fixed string graph as an induced minor. All of our results also hold for the stronger notion of Assouad--Nagata dimension, a refinement of asymptotic dimension. These results have a number of applications, two of which we mention here. First they imply that an induced minor-closed class is χ-bounded if and only if it does not contain some Burling graph. Second they imply that, in graph classes excluding a fixed planar graph as an induced minor, treewidth is polynomial in maximum degree.

An improved bound on the treewidth of planar graphs excluding a grid minor
Wouter Cames van Batenburg, Quentin Claus, Gwenaël Joret +3
arXiv14 Sep 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
Max Independent Set Remains NP-hard when Excluding a Planar Induced Minor
Édouard Bonnet, Yeonsu Chang
arXiv10 Sep 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
Unavoidable flats in matroids excluding a uniform minor
Wayne Ge
arXiv30 Oct 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
Induced Forest Minor Theorem for Graphs Without an Induced Star
Robert Hickingbotham, Gwenaël Joret
arXiv9 Sep 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
Revisiting separators in string graphs, region intersection graphs, and induced-minor-free graphs
James Davies, Paweł Rzążewski, Jack Spalding-Jamieson +1
arXiv16 Oct 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematics Geometry & topologyarXiv

Cite

BibTeX RIS

BibTeX

@misc{hickingbotham2026asymptotic,
  title = {{Asymptotic dimension of graphs excluding an induced or fat minor}},
  author = {Robert Hickingbotham and Freddie Illingworth and Piotr Micek and Bartosz Walczak},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.22495},
  eprint = {2610.22495},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.22495},
}

RIS

TY  - UNPB
TI  - Asymptotic dimension of graphs excluding an induced or fat minor
AU  - Robert Hickingbotham
AU  - Freddie Illingworth
AU  - Piotr Micek
AU  - Bartosz Walczak
PY  - 2026
DA  - 2026/10/15
PB  - arXiv
DO  - 10.48550/arxiv.2610.22495
UR  - https://arxiv.org/abs/2610.22495
AB  - Asymptotic dimension is a large-scale invariant of metric spaces that was introduced by Gromov (1993). A major open problem in coarse graph theory asks whether, for every fixed graph H, the class of graphs excluding H as a fat minor has bounded asymptotic dimension. A weaker conjecture asserts the same conclusion for graphs excluding H as an induced minor. We substantially expand the range of graphs H for which these conjectures are known to hold. Specifically, we prove bounded asymptotic dimension for the following classes of graphs: graphs excluding a fixed planar graph as a fat minor; and graphs excluding a fixed string graph as an induced minor. All of our results also hold for the stronger notion of Assouad--Nagata dimension, a refinement of asymptotic dimension. These results have a number of applications, two of which we mention here. First they imply that an induced minor-closed class is χ-bounded if and only if it does not contain some Burling graph. Second they imply that, in graph classes excluding a fixed planar graph as an induced minor, treewidth is polynomial in maximum degree.
ER  -

Abstract

Related

Cite