Homomorphism preservation on quasi-wide classes

DOI10.1016/j.jcss.2009.10.005zbMath1206.68140OpenAlexW1980240005WikidataQ58215527 ScholiaQ58215527MaRDI QIDQ980940

Anuj Dawar

Publication date: 8 July 2010

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2009.10.005

zbMATH Keywords

finite model theorybounded expansionhomomorphism preservationlocally excluded minorsquasi-wide classes

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Descriptive complexity and finite models (68Q19)

Related Items (10)

Characterising bounded expansion by neighbourhood complexity ⋮ On ultralimits of sparse graph classes ⋮ Fixed-parameter tractable distances to sparse graph classes ⋮ A generalization of the Łoś-Tarski preservation theorem ⋮ Interpreting nowhere dense graph classes as a classical notion of model theory ⋮ Reconfiguration on sparse graphs ⋮ Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-Wideness

Cites Work

• Datalog vs first-order logic
• Diameter and treewidth in minor-closed graph families
• Deciding first-order properties of locally tree-decomposable structures
• A counterexample to a conjecture of Scott and Suppes
• Preservation under Extensions on Well-Behaved Finite Structures
• The Grad of a Graph and Classes with Bounded Expansion
• Finite Model Theory on Tame Classes of Structures
• On preservation under homomorphisms and unions of conjunctive queries
• Homomorphism preservation theorems
• Monotone versus positive
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Homomorphism preservation on quasi-wide classes