The structure of the models of decidable monadic theories of graphs (Q810005)

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.