Two consequences of the dichotomy theorem on first order definability of graphs.

zbMath1066.03042MaRDI QIDQ1776035

O. V. Verbitskiĭ

Publication date: 20 May 2005

Published in: Matematychni Studiï (Search for Journal in Brave)

zbMATH Keywords

computational complexitygraphdichotomyEhrenfeucht game

Mathematics Subject Classification ID

Applications of game theory (91A80) Complexity of computation (including implicit computational complexity) (03D15) Model theory of finite structures (03C13) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Descriptive complexity and finite models (68Q19)

This page was built for publication: Two consequences of the dichotomy theorem on first order definability of graphs.