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

DOI10.1016/j.tcs.2005.05.003zbMath1083.03039arXivmath/0401361MaRDI QIDQ2570131

Oleg Verbitsky

Publication date: 26 October 2005

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/0401361

zbMATH Keywords

planar graphs; first-order definability; Ehrenfeucht game; graph separators

Mathematics Subject Classification ID

91A43: Games involving graphs

05C10: Planar graphs; geometric and topological aspects of graph theory

03C13: Model theory of finite structures

03C07: Basic properties of first-order languages and structures

68Q19: Descriptive complexity and finite models

Related Items

The first order definability of graphs: Upper bounds for quantifier depth, Decomposable graphs and definitions with no quantifier alternation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The first order definability of graphs: Upper bounds for quantifier depth
• Definability with bounded number of bound variables
• An optimal lower bound on the number of variables for graph identification
• Parallel concepts in graph theory
• Graph minors. XIII: The disjoint paths problem
• Succinct definitions in the first order theory of graphs
• Isomorphism testing for embeddable graphs through definability
• A separator theorem for graphs of bounded genus
• An application of games to the completeness problem for formalized theories
• Graph minors. II. Algorithmic aspects of tree-width
• A Separator Theorem for Planar Graphs
• A Separator Theorem for Nonplanar Graphs
• Planar Separators
• How complex are random graphs in first order logic?
• Treewidth and Pathwidth of Permutation Graphs
• Generating Outerplanar Graphs Uniformly at Random
• The strange logic of random graphs