Descriptive complexity: 3-colorability example
The convention in descriptive complexity is that for graph properties, the universe always consists of the set of vertices, and there is an additional two-place edge relation.