The first order definability of graphs with separators via the Ehrenfeucht game
From MaRDI portal
Publication:2570131
DOI10.1016/j.tcs.2005.05.003zbMath1083.03039arXivmath/0401361MaRDI QIDQ2570131
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
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