On the definability of properties of finite graphs

DOI10.1016/0012-365X(84)90166-3zbMath0536.05060MaRDI QIDQ791548

György Turán

Publication date: 1984

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

complexityHamiltonian graphsdefinability of graph-properties

Mathematics Subject Classification ID

Graph theory (05C99) Eulerian and Hamiltonian graphs (05C45) General logic (03B99)

Related Items

Arity and alternation in second-order logic ⋮ First-order logic axiomatization of metric graph theory ⋮ Finite-model theory -- A personal perspective ⋮ The descriptive complexity of subgraph isomorphism without numerics ⋮ On winning strategies in Ehrenfeucht-Fraïssé games ⋮ The closure of monadic NP

Cites Work

• Disjoint paths in graphs
• Number of quantifiers is better than number of tape cells
• Mechanizing hypothesis formation. Mathematical foundations for a general theory
• The computational complexity of logical theories
• Model theory
• Monadic generalized spectra
• Application of model theoretic games to discrete linear orders and finite automata
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item