What type of study is this?

This is a Quantitative Study study.

September 16, 2025

Proper minor-closed classes of graphs have Assouad–Nagata dimension 2

Key Points

Proper minor-closed classes of graphs exhibit an Assouad–Nagata dimension of 2, indicating a consistent large-scale structure.
The study extends prior findings showing that any such class has asymptotic dimension 2, linked to properties like treewidth.
Graph classes defined by subdivisions also demonstrate consistent Assouad–Nagata dimensions, further characterizing their structure.
Results suggest that conditions around treewidth significantly influence dimensional properties in graph classes.

Abstract

Abstract Asymptotic dimension and Assouad–Nagata dimension are measures of the large-scale shape of a class of graphs. Bonamy, Bousquet, Esperet, Groenland, Liu, Pirot, and Scott J. Eur. Math. Society showed that any proper minor-closed class has asymptotic dimension 2, dropping to 1 only if the treewidth is bounded. We improve this result by showing it also holds for the stricter Assouad–Nagata dimension. We also characterise when subdivision-closed classes of graphs have bounded Assouad–Nagata dimension.

Mark Helpful

Bookmark

Relay