On first-order definitions of subgraph isomorphism properties

DOI10.1134/S1064562417050167MaRDI QIDQ679970zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• First-order definitions of subgraph isomorphism through the adjacency and order relations
• On the first-order complexity of induced subgraph isomorphism
• Logical complexity of induced subgraph isomorphism for certain families of graphs

Cites work

• scientific article; zbMATH DE number 3910446 (Why is no real title available?)
• scientific article; zbMATH DE number 1072414 (Why is no real title available?)
• scientific article; zbMATH DE number 1432797 (Why is no real title available?)
• Elements of finite model theory.
• Polynomial bounds for the grid-minor theorem
• Random graphs: models and asymptotic characteristics
• Strong computational lower bounds via parameterized complexity
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Zero-one \(k\)-law

Cited in

(4)

• First-order definitions of subgraph isomorphism through the adjacency and order relations
• First-order complexity of subgraph isomorphism via Kneser graphs
• Logical complexity of induced subgraph isomorphism for certain families of graphs
• Tight bounds on the asymptotic descriptive complexity of subgraph isomorphism

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q679970)