Obstructions for Minor-Closed Classes of limiting Densities Below 3/2

Abstract

Given a graph class $\mathcal{G}$, the limiting density of $\mathcal{G}$ is defined as $\hat{I}´(\mathcal{G})={\lim }_{n\to \infty }\mathsf{ex}(\mathcal{G},n)/n$ where $\mathsf{ex}(\mathcal{G},n)$ is the maximum number of edges of a graph in $\mathcal{G}$ on $n$ vertices. The limiting density $\hat{I}´(\mathcal{G})$ is known to be a rational number when $\mathcal{G}$ is a minor-closed graph class. For every $\hat{I}´\in [0,\frac{3}{2})$, we prove that the set of $\subseteq$-minimal minor-closed graph classes with densities $>\hat{I}´$ is finite and we identify it completely. A consequence of our results is an algorithm that, given a finite set of graphs $\mathcal{Z}$, of total size $n$, either outputs the value of $\hat{I}´(\mathsf{excl}(\mathcal{Z}))$ or reports that $\hat{I}´(\mathsf{excl}(\mathcal{Z}))\ge \frac{3}{2}$, where $\mathsf{excl}(\mathcal{Z})$ is the class of graphs excluding the graphs in $\mathcal{Z}$ as minors. The algorithm runs in $2^{\mathsf{poly}(n)}$ time.

An extended abstract has been presented at WG 2026