The first order definability of graphs with separators via the Ehrenfeucht game

2005/06/15 by Oleg Verbitsky · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Bounded function #Combinatorics #Complexity and Algorithms in Graphs #Discrete mathematics #Graph #Limits and Structures in Graph Theory #Line graph #Mathematics #Outerplanar graph #Pathwidth #Planar graph #Upper and lower bounds

paper · pdf · doi:10.1016/j.tcs.2005.05.003

openalex publication_date 2005/06/15 · crossref created 2005/06/15 · crossref issued 2005/10/01 · crossref published 2005/10/01 · crossref published-print 2005/10/01 · crossref deposited 2023/05/03 · crossref indexed 2025/06/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/03

Citations

• Succinct definitions in the first order theory of graphs
• An optimal lower bound on the number of variables for graph identification
• The Strange Logic of Random Graphs
• A separator theorem for nonplanar graphs

Cited by

• Logic of graphs [wikipedia]