Nowhere dense graph classes, stability, and the independence property
classification
🧮 math.LO
cs.DMcs.LO
keywords
stabilityclassesdensegraphgraphsindependencenotionnowhere
read the original 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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.