Vertex-minors, monadic second-order logic, and a conjecture by Seese (Q858683): Difference between revisions

In many previous papers by the authors and others, it has been shown that for classes of graphs there are strong connections between the tractability of some graph problems, definability in monadic second-order (MS) logic, and the fact that some parameter, like the tree-width or the clique-width, is bounded. Here it is shown that, for any fixed \(k\), the class of (finite, undirected, simple) graphs with rank-width at most \(k\) can be defined by a formula of an MS logic augmented with a parity-counting predicate. Combined with some earlier results, this fact yields a polynomial-time algorithm for deciding whether a graph has rank-width at most \(k\). Moreover, the authors prove that if the satisfiability problem of the above extended MS logic is decidable for a class of graphs, then that class is contained in the image of a class of trees under an MS transduction, and it has bounded clique-width and bounded rank-width; this is a weaker form of a conjecture by D. Seese. In the proofs, isotropic systems are extensively used.