The monadic second-order logic of graphs XV: On a conjecture by D. Seese |
| |
Authors: | Bruno Courcelle |
| |
Affiliation: | LaBRI, CNRS and Bordeaux 1 University, 351 cours de la Libération, F-33405 Talence, France |
| |
Abstract: | A conjecture by D. Seese states that if a set of graphs has a decidable monadic second-order theory, then it is the image of a set of trees under a transformation of relational structures defined by monadic second-order formulas, or equivalently, has bounded clique-width. We prove that this conjecture is true if and only if it is true for the particular cases of bipartite undirected graphs, of directed graphs, of partial orders and of comparability graphs. We also prove that it is true for line graphs, for interval graphs and for partial orders of dimension 2. Our treatment of certain countably infinite graphs uses a representation of countable linear orders by binary trees that can be constructed by monadic second-order formulas. By using a counting argument, we show the intrinsic limits of the methods used here to handle this conjecture. |
| |
Keywords: | Graph Clique-width Comparability graph Line graph Interval graph Monadic second-order logic Decidable theory Monadic second-order transduction |
本文献已被 ScienceDirect 等数据库收录! |
|