Geodesic
Logical complexity of induced subgraph isomorphism for certain families of graphs
Sbornik. Mathematics, Tome 212 (2021) no. 4, pp. 517-530

Voir la notice de l'article provenant de la source Math-Net.Ru

We investigate the problem of the most efficient first-order definition of the property of containing an induced subgraph isomorphic to a given pattern graph, which is closely related to the time complexity of the decision problem for this property. We derive a series of new bounds for the minimum quantifier depth of a formula defining this property for pattern graphs on five vertices, as well as for disjoint unions of isomorphic complete multipartite graphs. Moreover, we prove that for any $\ell\geqslant 4$ there exists a graph on $\ell$ vertices and a first-order formula of quantifier depth at most $\ell-1$ that defines the property of containing an induced subgraph isomorphic to this graph. Bibliography: 12 titles.
Keywords: first-order formula, quantifier depth, induced subgraph, logical complexity. 
@article{SM_2021_212_4_a3,
     author = {M. E. Zhukovskii and E. D. Kudryavtsev and M. V. Makarov and A. S. Shlychkova},
     title = {Logical complexity of induced subgraph isomorphism for certain families of graphs},
     journal = {Sbornik. Mathematics},
     pages = {517--530},
     publisher = {mathdoc},
     volume = {212},
     number = {4},
     year = {2021},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SM_2021_212_4_a3/}
}
TY  - JOUR
AU  - M. E. Zhukovskii
AU  - E. D. Kudryavtsev
AU  - M. V. Makarov
AU  - A. S. Shlychkova
TI  - Logical complexity of induced subgraph isomorphism for certain families of graphs
JO  - Sbornik. Mathematics
PY  - 2021
SP  - 517
EP  - 530
VL  - 212
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SM_2021_212_4_a3/
LA  - en
ID  - SM_2021_212_4_a3
ER  - 
%0 Journal Article
%A M. E. Zhukovskii
%A E. D. Kudryavtsev
%A M. V. Makarov
%A A. S. Shlychkova
%T Logical complexity of induced subgraph isomorphism for certain families of graphs
%J Sbornik. Mathematics
%D 2021
%P 517-530
%V 212
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SM_2021_212_4_a3/
%G en
%F SM_2021_212_4_a3
M. E. Zhukovskii; E. D. Kudryavtsev; M. V. Makarov; A. S. Shlychkova. Logical complexity of induced subgraph isomorphism for certain families of graphs. Sbornik. Mathematics, Tome 212 (2021) no. 4, pp. 517-530. http://geodesic.mathdoc.fr/item/SM_2021_212_4_a3/