Logical complexity of induced subgraph isomorphism for certain families of graphs

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.