Abstract
We show how pebble games, Ehrenfeuch-Fraisse games and bisimulation games can be expressed as indexed comonads on the category of relational structures and homomorphisms.
This leads to syntax-free characterizations of the elementary equivalences for a range of logics, and to structural characterizations of tree-width, tree-depth and other combinatorial invariants in terms of the coalgebra numbers for structures with respect to the appropriate comonad.