First order properties on nowhere dense structures

DOI10.2178/jsl/1278682204zbMath1206.03033OpenAlexW2099898495MaRDI QIDQ4931094

Jaroslav Nešetřil, Patrice Ossona de Mendez

Publication date: 4 October 2010

Published in: The Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.141.4974

zbMATH Keywords

finite graphsfinite structureshomomorphism preservation theorem

Mathematics Subject Classification ID

Model theory of finite structures (03C13)

Related Items (30)

Enumeration for FO Queries over Nowhere Dense Graphs ⋮ Modeling limits in hereditary classes: reduction and application to trees ⋮ Triangle-free planar graphs with small independence number ⋮ Kernelization using structural parameters on sparse graph classes ⋮ Reconfiguration on nowhere dense graph classes ⋮ Towards a characterization of universal categories ⋮ First-order limits, an analytical perspective ⋮ A Unified Approach to Structural Limits and Limits of Graphs with Bounded Tree-Depth ⋮ Parameterized complexity of generalized domination problems ⋮ On nowhere dense graphs ⋮ Bounds on half graph orders in powers of sparse graphs ⋮ Interpreting nowhere dense graph classes as a classical notion of model theory ⋮ How many \(F\)'s are there in \(G\)? ⋮ Classes of graphs with low complexity: the case of classes with bounded linear rankwidth ⋮ Characterisations and examples of graph classes with bounded expansion ⋮ FPT algorithms for domination in sparse graphs and beyond ⋮ Reconfiguration on sparse graphs ⋮ On classes of graphs with strongly sublinear separators ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the parameterized complexity of \([1,j\)-domination problems] ⋮ Lossy Kernels for Connected Dominating Set on Sparse Graphs ⋮ Large Independent Sets in Triangle-Free Planar Graphs ⋮ EXISTENCE OF MODELING LIMITS FOR SEQUENCES OF SPARSE STRUCTURES ⋮ On the Parameterized Complexity of [1,j-Domination Problems] ⋮ Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness ⋮ Lossy Kernels for Connected Dominating Set on Sparse Graphs ⋮ Counting Homomorphisms to Sparse Graphs ⋮ Unnamed Item ⋮ Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-Wideness

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• An interpolation theorem in the predicate calculus
• On forbidden subdivision characterizations of graph classes
• Duality theorems for finite structures (characterising gaps and good characterisations)
• Grad and classes with bounded expansion. I: Decompositions
• Grad and classes with bounded expansion. II: Algorithmic aspects
• Grad and classes with bounded expansion. III: Restricted graph homomorphism dualities
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Finite Model Theory on Tame Classes of Structures
• On preservation under homomorphisms and unions of conjunctive queries
• Monotone versus positive
• Short Answers to Exponentially Long Questions: Extremal Aspects of Homomorphism Duality

This page was built for publication: First order properties on nowhere dense structures