Monadic second-order definable graph orderings

Achim Blumensath, Bruno Courcelle

We study the question of whether, for a given class of finite graphs, one can define, for each graph of the class, a linear ordering in monadic second-order logic, possibly with th…