CS Paper Radar

Asymptotic dimension of graphs excluding an induced or fat minor

Robert Hickingbotham, Freddie Illingworth, Piotr Micek, Bartosz Walczak

cs.DM math.CO ·submitted 2026-10-15 18:00 UTC · v1
theory

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Tight B-Trees for Adjacency Labeling

cs.DS cs.DM ·2026-11-08 ·Noy Rotbart
similarity 0.71
Abstract · 8 pages, 2 figures

We show that planar graphs admit adjacency labels of size $\log n+O(\log\log n)$: every vertex gets a label of this many bits, and the adjacency of two vertices is decided from their labels alone, in constant time. This improves the $\log n+O(\sqrt{\log n\log\log n})$ of Dujmović et al. (J. ACM 2021) and the $\log n+O(\sqrt{\log n})$ of Gawrychowski and Janczewski (SOSA 2022). Equivalently, $n$-vertex planar graphs have an induced-universal graph with $n(\log n)^{O(1)}$ vertices, down from $n2^{O(\sqrt{\log n})}$. The same holds for graphs of bounded genus, apex-minor-free graphs and $k$-planar graphs. For every proper minor-closed class we get $\log n+O(\sqrt{\log n\log\log n})$, down from the $\log n+O((\log n)^{3/4})$ of Dujmović et al. (2026). Both results come from tight B-trees: nodes are split into parts of nearly equal size, so every node but the topmost stays within a factor $1\pm O(1/\log n)$ of its target size, and a root-to-leaf path loses only $O(\log\log n)$ bits.

0.24

Three trees suffice for a constant stretch in minor-free graphs

cs.DS cs.CG ·2026-08-13 ·Hung Le, Huy Pham, Cuong Than, Tuan Tran
theory similarity 0.70
Abstract

In this short note, we show that $H$-minor-free graphs have a tree cover with $3$ trees and constant stretch for any fixed graph $H$. The number of trees matches the recent lower bound by Chen, Tan, and Xu who showed that a toroidal grid requires at least $3$ trees for constant stretch. Our result is obtained by establishing a connection between tree covers and Assouad--Nagata dimension and then invoking the recent dimension bound for minor-free metrics by Liu.

0.32

On (Pathwidth, Clique)-boundedness

cs.DM math.CO ·2026-11-17 ·Amir Nikabadi
theory similarity 0.69
Abstract

We prove that every $(\pw,ω)$-bounded class of graphs has bounded tree-independence number, answering a question of Bešter Štorgel, Dallard, Lozin, Milanič, and Zamaraev. We deduce this from a bound on the tree-independence number of graphs with neither $\B_ρ$ nor $K_{σ,σ}$ as an induced minor, where $\B_ρ$ is the complete binary tree of height $ρ$ and the bound depends only on $ρ$ and $σ$. We then obtain an asymptotically sharp bound on the path-independence number of $n$-vertex graphs in any $(\pw,ω)$-bounded class. The lower-bound examples also give counterexamples to a conjecture of Hickingbotham and Joret. We further prove that, for every forest $F$ and every $\ell\in\N$, there is a constant $k=k(F,\ell)\in\N$ such that every graph $G$ with no induced theta or $\ell$-long prism and no induced subgraph isomorphic to $F$ satisfies tree-independence number at most $k$. This proves a strengthened form of a conjecture of Chudnovsky, Hajebi, and Trotignon. Finally, for every integer $s\ge2$, we characterize the forests $F$ for which excluding $F$ as an induced minor and $K_{s,s}$ as an induced subgraph bounds tree-independence number. This extends the characterization of Bonnet, Duhamel, and Hickingbotham, who considered bounded pathwidth with $K_{s,s}$ excluded as a subgraph.

0.07

Small classes have linear neighbourhood complexity

cs.DM math.CO ·2026-11-11 ·John Sylvester, Viktor Zamaraev, Maksim Zhukovskii
theory similarity 0.67
Abstract · 31 pages, 6 figures

A hereditary graph class is small if it contains at most $n!c^n$ labelled graphs on $n$ vertices for some constant $c$. Small classes include proper minor-closed classes and classes of bounded twin-width. We prove that every small class has linear neighbourhood complexity, that is, in every graph in the class, vertex neighbourhoods intersect any $k$-vertex set in only $O(k)$ distinct ways. This resolves a conjecture of Bonnet, Duron, and the first two authors (ITCS 2025) and makes the algorithmic, structural, and representation consequences of linear neighbourhood complexity available for every small class. In particular, every small class admits an adjacency labelling scheme with $O(\log^2 n)$-bit labels, improving the previous $O(\log^3 n)$ bound.

0.22

You Can Have It All: Small sparse induced-universal graphs for minor-closed classes

cs.DM math.CO ·2026-11-10 ·Vida Dujmović, Cyril Gavoille, Gwenaël Joret, Piotr Micek, Pat Morin +1 more
similarity 0.67
Abstract · Extends the results in arXiv:2605.06616 to produce induced-universal graphs with $n^{1+o(1)}$ edges and vertices

We show that, for every fixed proper minor-closed graph class $\mathcal{G}$ and every positive integer $n$, there exists a graph $U_n$ with $n^{1+o(1)}$ vertices and edges such that every $n$-vertex graph in $\mathcal{G}$ is isomorphic to an induced subgraph of $U_n$. This result generalizes and unifies the results of Dujmović et al. (J. ACM 2021) on induced-universal graphs and the results of Esperet, Joret, and Morin (J. London Math. Soc. 2023) on sparse induced-universal graphs from planar graphs to all proper minor-closed graph classes. It simultaneously improves the previous bounds for the number of vertices in induced-universal graphs (previously $O(n^2)$ obtained as a corollary of a result of DeVos et al. (J. Comb. Theory, Ser. {B} 2004) and a result of Gavoille and Labourel (ESA 2007)) and the number of edges in subgraph-universal graphs (previously $O(n^{3/2})$ by Babai et al. (Theory and Practice of Combinatorics 1982)).

0.20

Almost tight distributed approximation for domination in sparse graph classes

cs.DC cs.DMcs.DS ·2026-10-22 ·Timothé Picavet
similarity 0.65
Abstract · 27 pages, 4 figures

We study distributed approximation of Minimum Dominating Set in a very general class of sparse graphs, extending near-optimal approximation results from the minor-free setting to bounded expansion. In more detail, for fixed $d$ and $\varepsilon>0$, we give a new deterministic constant-round LOCAL algorithm for Minimum Dominating Set on graphs of maximum average degree at most $d$ and bounded depth-one shallow-minor density. Its approximation ratio is $d+1+\varepsilon$, which is optimal up to $\varepsilon$ for every even integer $d\geq 2$. This improves on the recent results of Amiri and Siebertz by extending beyond proper minor-closed classes. From this algorithm, we derive almost-tight constant-round approximations for a number of graph classes. We get $(7+\varepsilon)$-approximations for planar graphs and graphs of bounded Euler genus, and $(5+\varepsilon)$-approximations for their triangle-free subclasses. This answers the $7+\varepsilon$ question of Wawrzyniak positively, and matches the recent results of Amiri and Siebertz. We also apply our algorithm to classes of bounded queue-number or stack-number, obtaining bounds that are tight up to $\varepsilon$. Additionally, we answer questions of Amiri and Siebertz about improving the dependence of the round complexity on $1/\varepsilon$ and obtaining polynomial local computation for fixed parameters, when comparing the output to the usual domination number.

0.33

Countable Graphs with Finite Path-width: Characterisation and Universality

cs.DM math.CO ·2026-08-27 ·Tony Huynh, Freddie Illingworth, Nikolai Karol, Florian Lehner, Chun-Hung Liu +2 more
theory similarity 0.65
Abstract

We study path-width and the closely related parameter line-width in countably infinite graphs. Our first result characterises the graphs of finite path-width: they are the graphs that do not have infinitely many vertices of infinite degree, do not have infinitely many pairwise disjoint infinite paths, and contain no subdivision of some finite tree of maximum degree 3. We then investigate universality under the subgraph relation for graphs of bounded path-width or line-width. In particular, we prove that there exists a universal graph with line-width $\mathcal{O}(k^2)$ for the class of graphs with line-width at most $k$. In contrast, we show that no graph of finite path-width is universal for the class of locally finite graphs with path-width $1$. Finally, we show that for each $k\geq 2$, every universal graph for the class of graphs with path-width at most $k$ has line-width at least $k + 1$.

0.14

Exploring Minimal Blocking Sets for Kernelization Lower Bounds for $\mathcal{F}$-Minor Deletion

cs.DS cs.CC ·2026-10-13 ·Ahmed Ghazy, Jakob Greilhuber, Tim A. Hartmann
similarity 0.65
Abstract · Full version of an IPEC 2026 contribution. Abstract has been shortened for arXiv

For Vertex Cover, a minimal blocking set of a graph $G$ is an inclusion-wise minimal vertex set contained in no minimum vertex cover of $G$. Bougeret et al. [SIDMA 2022] showed that, for all minor-closed graph classes $\mathcal{G}$, Vertex Cover has a polynomial kernel parameterized by the distance to $\mathcal{G}$ if and only if $\mathcal{G}$ has bounded minimal blocking sets. In this work, we explore how far this connection between minimal blocking sets and kernelization extends to $\mathcal{F}$-Minor Deletion parameterized by the deletion distance to $\mathcal{G}$. A minimal $\mathcal{F}$-blocking set of $G$ is a minimal vertex set not contained in any optimal $\mathcal{F}$-Minor Deletion solution of $G$. For connected families $\mathcal{F}$, we show that if some graph class $\mathcal{G}$ closed under disjoint union has unbounded minimal $\mathcal{F}$-blocking sets, then $\mathcal{F}$-Minor Deletion parameterized by the deletion distance to $\mathcal{G}$ has no polynomial kernel. This generalizes a result of Hols et al. [SIDMA 2022] for Vertex Cover. We then show that this criterion does not capture all kernelization lower bounds for $\mathcal{F}$-Minor Deletion, even for minor-closed graph classes. Motivated by the work of Dekker and Jansen [Discrete Appl. Math. 2024], we study the more general notion of extended $\mathcal{F}$-blocking sets and the kernelization lower bounds they yield. For every fixed integer $η\geq 1$, Pw-$η$ Deletion is the problem of deleting at most $k$ vertices to reduce the pathwidth to at most $η$. We show that it has no polynomial kernel parameterized by the distance to graphs with pathwidth at most $η+1$. Moreover, for connected families $\mathcal{F}$, we show that $\mathcal{F}$-Minor Deletion parameterized by the distance to graphs with pathwidth at most $\max_{F\in\mathcal{F}} pw(F)+1$ has no polynomial kernel.

0.26