It is well known that on classes of graphs of bounded tree-width, every monadic second-order property is decidable in polynomial time. The converse is not true without further assumptions. It follows from the work of Robertson and Seymour, that if a class of graphs K has unbounded tree-width and is closed under minors, then K contains all planar graphs. But on planar graphs, three-colorability is NP-complete. Hence, if P = NP and on K every existential monadic second-order property is in P, then K has bounded tree-width. In other words, for K closed under minors, K is of bounded tree-width i all monadic second-order properties are decidable in P.
In this note we prove that in order to characterize classes of graphs of bounded tree-width where the monadic quantiÿer hierarchy collapses, closure under minors can be replaced by closure under topological minors. Closure under minors of K implies that K is in P, whereas we also note that there is a class of graphs K closed under topological minors which is not even r.e.
We also show, that closure under induced subgraphs or even under subgraphs alone does not su ce to show that the collapse of the monadic quantiÿer hierarchy on K implies that K is of bounded tree-width or clique-width.
Other characterizations of classes of bounded tree-width in terms of collapses of the monadic quantiÿer hierarchy to levels above the existential are discussed.