The First Order Definability of Graphs with Separators via the Ehrenfeucht Game
| dc.creator | Verbitsky, Oleg | |
| dc.date | 2004-01-26 | |
| dc.date.accessioned | 2026-07-07T05:04:52Z | |
| dc.date.available | 2026-07-07T05:04:52Z | |
| dc.description | We say that a first order formula $Φ$ defines a graph $G$ if $Φ$ is true on $G$ and false on every graph $G'$ non-isomorphic with $G$. Let $D(G)$ be the minimal quantifier rank of a such formula. We prove that, if $G$ is a tree of bounded degree or a Hamiltonian (equivalently, 2-connected) outerplanar graph, then $D(G)=O(\log n)$, where $n$ denotes the order of $G$. This bound is optimal up to a constant factor. If $h$ is a constant, for connected graphs with no minor $K_h$ and degree $O(\sqrt n/\log n)$, we prove the bound $D(G)=O(\sqrt n)$. This result applies to planar graphs and, more generally, to graphs of bounded genus. | |
| dc.description | 17 pages | |
| dc.identifier | https://arxiv.org/abs/math/0401361 | |
| dc.identifier | http://arxiv.org/abs/math/0401361 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/69977 | |
| dc.subject | Combinatorics | |
| dc.subject | Logic | |
| dc.subject | 03C13; 05C60 | |
| dc.title | The First Order Definability of Graphs with Separators via the Ehrenfeucht Game | |
| dc.type | text |