First-Order Interpretations of Bounded Expansion Classes

DOI10.1145/3382093zbMath1446.68094arXiv1810.02389OpenAlexW3040059890MaRDI QIDQ5121280

Patrice Ossona de Mendez, Sebastian Siebertz, Michał Pilipczuk, Jakub Gajarský, Stephan Kreutzer, Szymon Toruńczyk, Jaroslav Nešetřil

Publication date: 11 September 2020

Published in: ACM Transactions on Computational Logic (Search for Journal in Brave)

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

zbMATH Keywords

first-order logicmodel-checkingbounded expansionsparse graph classeslogical interpretations

Mathematics Subject Classification ID

Logic in computer science (03B70) Specification and verification (program logics, model checking, etc.) (68Q60) Structural characterization of families of graphs (05C75)

Related Items (9)

Rainbow independent sets on dense graph classes ⋮ Twin-width II: small classes ⋮ Characterising graphs with no subdivision of a wheel of bounded diameter ⋮ Lacon-, Shrub- and Parity-Decompositions: Characterizing Transductions of Bounded Expansion Classes ⋮ Unnamed Item ⋮ Clustering powers of sparse graphs ⋮ Polynomial bounds for centered colorings on proper minor-closed graph classes ⋮ Erdös--Hajnal Properties for Powers of Sparse Graphs ⋮ From \(\chi\)- to \(\chi_p\)-bounded classes

This page was built for publication: First-Order Interpretations of Bounded Expansion Classes