On first-order definitions of subgraph isomorphism properties

DOI10.1134/S1064562417050167zbMath1423.03114OpenAlexW2766767719MaRDI QIDQ679970

M. E. Zhukovskii

Publication date: 22 January 2018

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

Full work available at URL: https://doi.org/10.1134/s1064562417050167

Mathematics Subject Classification ID

Graph theory (05C99) Model theory of finite structures (03C13) Connectivity (05C40) Basic properties of first-order languages and structures (03C07)

Related Items (1)

Logical complexity of induced subgraph isomorphism for certain families of graphs

Cites Work

• Zero-one \(k\)-law
• Elements of finite model theory.
• Strong computational lower bounds via parameterized complexity
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Polynomial bounds for the grid-minor theorem
• Random graphs: models and asymptotic characteristics
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On first-order definitions of subgraph isomorphism properties