1 citations · 2 across the 10 of their papers we have counts for
Showing 2004 · math.COShow all
3 papers · 2 filters
math.CO2004
On the Lengths of Symmetry Breaking-Preserving Games on Graphs
Frank Harary, Wolfgang Slany, Oleg Verbitsky
Given a graph , we consider a game where two players, and , alternatingly color edges of in red and in blue respectively. Let be the maximum number of moves in…
math.CO2004
The First Order Definability of Graphs with Separators via the Ehrenfeucht Game
Oleg Verbitsky
We say that a first order formula defines a graph if is true on and false on every graph non-isomorphic with . Let be the minimal quantifier rank of…
math.CO2004★ 1 cited
How Complex are Random Graphs in First Order Logic?
Jeong Han Kim, Oleg Pikhurko, Joel Spencer +1
It is not hard to write a first order formula which is true for a given graph G but is false for any graph not isomorphic to G. The smallest number $(G) of nested quantifiers in a…