On the number of types in sparse graphs

DOI10.1145/3209108.3209178zbMath1453.03031arXiv1705.09336OpenAlexW2798339057MaRDI QIDQ5145357

Szymon Toruńczyk, Sebastian Siebertz, Michał Pilipczuk

Publication date: 20 January 2021

Published in: Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1705.09336

zbMATH Keywords

stabilityStone spacenowhere dense graphsVC-densityfirst-order typesuniform quasi-wideness

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Classification theory, stability, and related concepts in model theory (03C45) Density (toughness, etc.) (05C42)

Related Items (13)

On the parameterized complexity of reconfiguration of connected dominating sets ⋮ Reconfiguration on nowhere dense graph classes ⋮ Kernelization and approximation of distance-\(r\) independent sets on nowhere dense graphs ⋮ Lacon-, Shrub- and Parity-Decompositions: Characterizing Transductions of Bounded Expansion Classes ⋮ Bounds on half graph orders in powers of sparse graphs ⋮ Unnamed Item ⋮ Regular partitions of gentle graphs ⋮ Classes of graphs with low complexity: the case of classes with bounded linear rankwidth ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness ⋮ Lossy Kernels for Connected Dominating Set on Sparse Graphs ⋮ Erdös--Hajnal Properties for Powers of Sparse Graphs

This page was built for publication: On the number of types in sparse graphs