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

05C80: Random graphs (graph-theoretic aspects)

03C13: Model theory of finite structures

05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)

68Q19: Descriptive complexity and finite models