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/0401361OpenAlexW1986313631MaRDI 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
Games involving graphs (91A43) Planar graphs; geometric and topological aspects of graph theory (05C10) Model theory of finite structures (03C13) Basic properties of first-order languages and structures (03C07) Descriptive complexity and finite models (68Q19)
Related Items (2)
The first order definability of graphs: Upper bounds for quantifier depth ⋮ Decomposable graphs and definitions with no quantifier alternation
Cites Work
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: The first order definability of graphs with separators via the Ehrenfeucht game
