First-order definitions of subgraph isomorphism through the adjacency and order relations

DOI10.2140/MOSCOW.2020.9.293zbMATH Open1472.03026OpenAlexW3099028489MaRDI QIDQ2211263FDOQ2211263

Authors: Oleg Grigoryan, Mikhail Makarov, M. E. Zhukovskii 

Publication date: 10 November 2020

Published in: Moscow Journal of Combinatorics and Number Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2140/moscow.2020.9.293

Recommendations

• On first-order definitions of subgraph isomorphism properties
• Logical complexity of induced subgraph isomorphism for certain families of graphs
• On the first-order complexity of induced subgraph isomorphism

zbMATH Keywords

first-order logicordersubgraph isomorphismdescriptive complexitysubtreelogical complexitylinearly ordered graphsquantifier depth

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Model theory of finite structures (03C13) Descriptive complexity and finite models (68Q19)

Cites Work

• Powers of tensors and fast matrix multiplication
• Color-coding
• Title not available (Why is that?)
• On the first-order complexity of induced subgraph isomorphism
• A short tutorial on order-invariant first-order logic
• Tight bounds on the asymptotic descriptive complexity of subgraph isomorphism

Cited In (6)

• The first order definability of graphs: Upper bounds for quantifier depth
• Logical complexity of induced subgraph isomorphism for certain families of graphs
• First-order complexity of subgraph isomorphism via Kneser graphs
• On the first-order complexity of induced subgraph isomorphism
• On the first-order complexity of induced subgraph isomorphism
• On first-order definitions of subgraph isomorphism properties

This page was built for publication: First-order definitions of subgraph isomorphism through the adjacency and order relations

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