Graphs Identified by Logics with Counting

Sandra Kiefer, Pascal Schweitzer, Erkal Selman

We classify graphs and, more generally, finite relational structures that are identified by C2, that is, two-variable first-order logic with counting. Using this classification, we…