Logical complexity of graphs: a survey

zbMath1261.03117arXiv1003.4865MaRDI QIDQ3118383

Oleg Pikhurko, Oleg Verbitsky

Publication date: 2 March 2012

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

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Model theory of finite structures (03C13) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Descriptive complexity and finite models (68Q19)

Related Items (6)

Bounds for the Quantifier Depth in Finite-Variable Logics ⋮ On the WL-dimension of circulant graphs of prime power order ⋮ Upper Bounds on the Quantifier Depth for Graph Differentiation in First Order Logic ⋮ Unnamed Item ⋮ The descriptive complexity of subgraph isomorphism without numerics ⋮ Defining long words succinctly in FO and MSO

This page was built for publication: Logical complexity of graphs: a survey