The monadic second-order logic of graphs. XV: On a conjecture by D. Seese (Q2494727)

[For the previous paper in this series see Zbl 1038.68046.] \textit{D. Seese} (1992; Zbl 0798.68059) has argued that low complexity and the decidability of the monadic second-order theory of a class of graphs correlate with the fact that the graphs somehow resemble trees. He conjectured that if a class of graphs has a decidable monadic second-order theory, then it is the image of a class of trees under a transformation definable by monadic second-order formulas. This property is known to be equivalent to bounded clique-width. The conjecture is still open but it has been established for the subclasses of some classes of graphs and the present paper contains several further results along these lines. For example, the equivalences between such relativizations to directed graphs, to partial orders, to bipartite graphs and to comparability graphs are proved. Furthermore, the validity of the conjecture is established for the classes of line graphs, directed line graphs, finite interval graphs, and a few other classes. Moreover, a weaker version of the conjecture is proved for certain countable graphs.