Abstract:Given a graph class $\mathcal{G}$, the limiting density of $\mathcal{G}$ is defined as $\delta(\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 $\delta(\mathcal{G})$ is known to be a rational number when $\mathcal{G}$ is a minor-closed graph class. For every $\delta\in[0,\frac{3}{2})$, we prove that the set of $\subseteq$-minimal minor-closed graph classes with densities $>\delta$ 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 $\delta(\mathsf{excl}(\mathcal{Z}))$ or reports that $\delta(\mathsf{excl}(\mathcal{Z}))\geq \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.
From: Dimitrios Thilikos [view email]
[v1]
Tue, 23 Jun 2026 09:02:50 UTC (45 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。