On first-order definitions of subgraph isomorphism properties

DOI10.1134/S1064562417050167zbMATH Open1423.03114OpenAlexW2766767719MaRDI QIDQ679970FDOQ679970

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

Recommendations

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (5)

• First-order definitions of subgraph isomorphism through the adjacency and order relations
• The descriptive complexity of subgraph isomorphism without numerics
• Logical complexity of induced subgraph isomorphism for certain families of graphs
• First-order complexity of subgraph isomorphism via Kneser 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)