Deciding first-order properties of nowhere dense graphs

DOI10.1145/2591796.2591851MaRDI QIDQ6829580zbMATH OpenFDO

Authors Martin Grohe, Stephan Kreutzer, Sebastian Siebertz

Publication date 26 June 2015

Published in Proceedings of the forty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2591796.2591851

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Density (toughness, etc.) (05C42) Games on graphs (graph-theoretic aspects) (05C57) Structural characterization of families of graphs (05C75)

Cited in

(4)

• On solution discovery via reconfiguration
• First-order transductions of graphs (invited talk)
• Parameterized shortest path reconfiguration
• Solving partial dominating set and related problems using twin-width

This page was built for publication: Deciding first-order properties of nowhere dense graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6829580)