The monadic second-order logic of graphs X: Linear orderings

Graphs are finite and handled as relational structures. We give some answers to the following general questions:

1. (1) For which classes of graphs is it possible to specify a linear ordering of the set of vertices of each graph of by fixed monadic second-order formulas?

2. (2) For which classes of graphs does there exist an extension of monadic second-order logic such that a subclass L of is recognizable if and only if it is the class of graphs in that satisfy a formula of ? (In this paper, recognizability is understood in an algebraic sense, relative to a finite set of graph operations and basic graphs that generate all graphs of .)

3. (3) For which classes of graphs is it possible to construct, in every graph of the class, and by fixed formulas of a suitable extension of monadic second-order logic, its hierarchichal structure, i.e., a finite term written with the operations and basic graphs of (2), that defines the considered graph?

Applications concern dependency graphs of partially commutative words, partial k-paths, cographs, and graphs, the modular decomposition of which uses prime graphs of bounded size.