Nowhere dense graph classes, stability, and the independence property

Abstract

A class of graphs is nowhere dense if for every integer r there is a finite upper bound on the size of cliques that occur as (topological) r-minors. We observe that this tameness notion from algorithmic graph theory is essentially the earlier stability theoretic notion of superflatness. For subgraph-closed classes of graphs we prove equivalence to stability and to not having the independence property.

arXiv comment9 pages

References in corpus (1)

• Finite models, stability, and Ramsey's theorem

Cited by in corpus (1)

• Tameness in least fixed-point logic and McColm's conjecture