1 citations · 2 across the 8 of their papers we have counts for
6 papers · 1 filter
On the Computational Complexity of the Forcing Chromatic Number
Frank Harary, Wolfgang Slany, Oleg Verbitsky
We consider vertex colorings of graphs in which adjacent vertices have distinct colors. A graph is -chromatic if it is colorable in colors and any coloring of it uses at lea…
Definitions with no quantifier alternation
Oleg Pikhurko, Joel Spencer, Oleg Verbitsky
Let be the minimum quantifier depth of a first order sentence that defines a graph up to isomorphism. Let be the version of where we do not allow qua…
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…
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…
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…
Succinct Definitions in the First Order Theory of Graphs
Oleg Pikhurko, Joel Spencer, Oleg Verbitsky
We say that a first order sentence A defines a graph G if A is true on G but false on any graph non-isomorphic to G. Let L(G) (resp. D(G)) denote the minimum length (resp. quantifi…