## The structure of the models of decidable monadic theories of graphs.(English)Zbl 0733.03026

The author devotes the bulk of this paper to a proof of the following undecidability result. If K is a class of graphs such that for each planar graph H there is a planar graph $$G\in K$$ with H isomorphic to a minor of G, then both the second-order monadic and weak second-order monadic theories of K are undecidable. This generalizes an earlier theorem of the author.
The author then quickly deduces that if the (weak) monadic theory of a class K of planar graphs is decidable then the tree-width of the graphs in K is universally bounded and there is a class T of trees such that the (weak) monadic theory of K is interpretable in the (weak) monadic theory of T. The paper ends with three open problems.

### MSC:

 03C65 Models of other mathematical theories 03B25 Decidability of theories and sets of sentences 05C99 Graph theory 05C05 Trees 05C10 Planar graphs; geometric and topological aspects of graph theory
Full Text: