2018/02/06 by Oleg Verbitsky, Verbitsky, Oleg, Maksim Zhukovskii +1 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithms and Data Compression #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Discrete mathematics #Graph #Graph isomorphism #Induced subgraph #Induced subgraph isomorphism problem #Isomorphism (crystallography) #Line graph #Mathematics #Order (exchange) #Quantifier (linguistics) #Subgraph isomorphism problem #Voltage graph #cs.CC #cs.LO
paper · pdf · doi:10.1145/3303881
22 pages, 3 figures
arxiv created 2018/02/06 · arxiv updated 2018/02/08 · openalex publication_date 2019/03/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
Let v(F) denote the number of vertices in a fixed connected pattern graph F. We show an infinite family of patterns F such that the existence of a subgraph isomorphic to F is expressible by a first-order sentence of quantifier depth \frac23 v(F)+1, assuming that the host graph is sufficiently large and connected. On the other hand, this is impossible for any F with using less than \frac23 v(F)-2 first-order variables.