2026-07-23T03:49:12Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26195 2026-07-02T07:14:09Z ddc:004 open_access

Obstructions for Minor-Closed Classes of Limiting Densities Below 3/2 Kominatos, Antonios Mahmoud, Reem Thilikos, Dimitrios M. Graph Minors Limiting density Obstruction set Class property Parametric graph Given a graph class 𝒢, the limiting density of 𝒢 is defined as δ(𝒢) = lim_{n → ∞} ex(𝒢,n)/n where ex(𝒢,n) is the maximum number of edges of a graph in 𝒢 on n vertices. The limiting density δ(𝒢) is known to be a rational number when 𝒢 is a minor-closed graph class. For every δ ∈ [0,3/2), we prove that the set of ⊆-minimal minor-closed graph classes with densities > δ is finite and we identify it completely. A consequence of our results is an algorithm that, given a finite set of graphs 𝒵, of total size n, either outputs the value of δ(excl(𝒵)) or reports that δ(excl(𝒵)) ≥ 3/2, where excl(𝒵) is the class of graphs excluding the graphs in 𝒵 as minors. The algorithm runs in 2^{poly(n)} time. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Antonios Kominatos and Reem Mahmoud and Dimitrios M. Thilikos 2026 Is Part Of LIPIcs, Volume 376, 52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.WG.2026.29 urn:nbn:de:0030-drops-261952 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WG.2026.29 eng https://creativecommons.org/licenses/by/4.0/legalcode