On the First-Order Complexity of Induced Subgraph Isomorphism

Oleg Verbitsky, Maksim Zhukovskii

Given a graph $F$, let $I(F)$ be the class of graphs containing $F$ as an induced subgraph. Let $W[F]$ denote the minimum $k$ such that $I(F)$ is definable in $k$-variable first-or…