The monadic second-order logic of graphs. XV: On a conjecture by D. Seese

DOI10.1016/J.JAL.2005.08.004MaRDI QIDQ2494727zbMATH OpenOpenAlexWikidataFDO

Authors Bruno Courcelle

Publication date 30 June 2006

Published in Journal of Applied Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jal.2005.08.004

zbMATH Keywords

clique-widthcomparability graphdecidable theoryinterval graphline graphmonadic second-order logicmonadic second-order transductiontree definability

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Graph theory (05C99)

Review text

[For the previous paper in this series see Zbl 1038.68046.] \textit{D. Seese} (1992; Zbl 0798.68059) has argued that low complexity and the decidability of the monadic second-order theory of a class of graphs correlate with the fact that the graphs somehow resemble trees. He conjectured that if a class of graphs has a decidable monadic second-order theory, then it is the image of a class of trees under a transformation definable by monadic second-order formulas. This property is known to be equivalent to bounded clique-width. The conjecture is still open but it has been established for the subclasses of some classes of graphs and the present paper contains several further results along these lines. For example, the equivalences between such relativizations to directed graphs, to partial orders, to bipartite graphs and to comparability graphs are proved. Furthermore, the validity of the conjecture is established for the classes of line graphs, directed line graphs, finite interval graphs, and a few other classes. Moreover, a weaker version of the conjecture is proved for certain countable graphs.

Recommendations

• Vertex-minors, monadic second-order logic, and a conjecture by Seese
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• The monadic second-order logic of graphs, II: Infinite graphs of bounded width
• The structure of the models of decidable monadic theories of graphs
• Clique-width of countable graphs: A compactness property.

Cites work

• A monadic second-order definition of the structure of convex hypergraphs.
• A partial k-arboretum of graphs with bounded treewidth
• Characterization problems for graphs, partially ordered sets, lattices, and families of sets
• Clique-width of countable graphs: A compactness property.
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Efficient graph representations
• Erratum to ``The monadic second-order logic of graphs. VI: On several representations of graphs by relational structures
• Fusion in relational structures and the verification of monadic second-order properties
• Graph Classes: A Survey
• Graph minors. V. Excluding a planar graph
• Handbook of Graph Grammars and Computing by Graph Transformation
• Highly connected sets and the excluded grid theorem
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3906240 (Why is no real title available?)
• scientific article; zbMATH DE number 53952 (Why is no real title available?)
• scientific article; zbMATH DE number 475414 (Why is no real title available?)
• scientific article; zbMATH DE number 729555 (Why is no real title available?)
• scientific article; zbMATH DE number 1136093 (Why is no real title available?)
• scientific article; zbMATH DE number 809155 (Why is no real title available?)
• scientific article; zbMATH DE number 6157240 (Why is no real title available?)
• scientific article; zbMATH DE number 1432797 (Why is no real title available?)
• scientific article; zbMATH DE number 3218572 (Why is no real title available?)
• LATIN 2004: Theoretical Informatics
• Linear time solvable optimization problems on graphs of bounded clique-width
• Logical description of context-free graph languages
• Monadic second-order definable graph transductions: a survey
• N-free posets as generalizations of series-parallel posets
• The monadic second-order logic of graphs, II: Infinite graphs of bounded width
• The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability
• The monadic second-order logic of graphs. VIII: Orientations
• The monadic second-order logic of graphs. X: Linear orderings
• The monadic second-order logic of graphs. XIV: Uniformly sparse graphs and edge set quantifica\-tions.
• The structure of the models of decidable monadic theories of graphs
• Upper bounds to the clique width of graphs
• Vertex-minors, monadic second-order logic, and a conjecture by Seese

Cited in

(17)

• The monadic second-order logic of graphs. XIV: Uniformly sparse graphs and edge set quantifica\-tions.
• Constrained-path labellings on graphs of bounded clique-width
• On quasi-planar graphs: clique-width and logical description
• Fixed-treewidth-efficient algorithms for edge-deletion to interval graph classes
• Rabin's theorem in the concurrency setting: a conjecture
• The rank-width of edge-coloured graphs
• The modular decomposition of countable graphs. Definition and construction in monadic second-order logic
• The monadic second-order logic of graphs, II: Infinite graphs of bounded width
• Betweenness of partial orders
• The behavior of clique-width under graph operations and graph transformations
• On spectra of sentences of monadic second order logic with counting
• MSO undecidability for hereditary classes of unbounded clique width
• MSO undecidability for hereditary classes of unbounded clique-width
• The monadic second-order logic of graphs. IX: Machines and their behaviours
• The structure of the models of decidable monadic theories of graphs
• Vertex-minors, monadic second-order logic, and a conjecture by Seese
• Circle graphs and monadic second-order logic

This page was built for publication: The monadic second-order logic of graphs. XV: On a conjecture by D. Seese

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2494727)