DROPS

Document

DOI: 10.4230/LIPIcs.WG.2026.29

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

Authors: Antonios Kominatos, Reem Mahmoud, and Dimitrios M. Thilikos

Published in: LIPIcs, Volume 376, 52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026)

Abstract

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.

Cite as

Antonios Kominatos, Reem Mahmoud, and Dimitrios M. Thilikos. Obstructions for Minor-Closed Classes of Limiting Densities Below 3/2. In 52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 376, pp. 29:1-29:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{kominatos_et_al:LIPIcs.WG.2026.29,
  author =	{Kominatos, Antonios and Mahmoud, Reem and Thilikos, Dimitrios M.},
  title =	{{Obstructions for Minor-Closed Classes of Limiting Densities Below 3/2}},
  booktitle =	{52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026)},
  pages =	{29:1--29:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-430-7},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{376},
  editor =	{Goedgebeur, Jan and Rz\k{a}\.{z}ewski, Pawe{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WG.2026.29},
  URN =		{urn:nbn:de:0030-drops-261952},
  doi =		{10.4230/LIPIcs.WG.2026.29},
  annote =	{Keywords: Graph Minors, Limiting density, Obstruction set, Class property, Parametric graph}
}

Search Results

Documents authored by Kominatos, Antonios

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

Abstract

Cite as

Thanks for your feedback!

Could not send message