MSO undecidability for hereditary classes of unbounded clique-width

DOI10.1016/J.EJC.2023.103700MaRDI QIDQ6614399zbMATH OpenFDO

Authors Anuj Dawar, Abhisekh Sankaran

Publication date 7 October 2024

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.EJC.2023.103700

zbMATH Keywords

monadic second-order logicSeese's conjecture

Mathematics Subject Classification ID

Higher-order logic (03B16) Decidability of theories and sets of sentences (03B25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Structural characterization of families of graphs (05C75)

Recommendations

• MSO undecidability for hereditary classes of unbounded clique width
• The monadic second-order logic of graphs. XV: On a conjecture by D. Seese
• Vertex-minors, monadic second-order logic, and a conjecture by Seese
• On the Parameterised Intractability of Monadic Second-Order Logic
• The structure of the models of decidable monadic theories of graphs

Cites work

• A new graph construction of unbounded clique-width
• Approximating clique-width and branch-width
• Clique-width: when hard does not mean impossible
• From tree-decompositions to clique-width terms
• Graph minors. XX: Wagner's conjecture
• Graph structure and monadic second-order logic. A language-theoretic approach
• Handle-rewriting hypergraph grammars
• scientific article; zbMATH DE number 53151 (Why is no real title available?)
• Infinitely many minimal classes of graphs of unbounded clique-width
• Minimal classes of graphs of unbounded clique-width
• Minimal classes of graphs of unbounded clique-width defined by finitely many forbidden induced subgraphs
• On the Parameterised Intractability of Monadic Second-Order Logic
• On the Relationship Between Clique-Width and Treewidth
• Sparsity. Graphs, structures, and algorithms
• The monadic second-order logic of graphs. XV: On a conjecture by D. Seese
• The structure of the models of decidable monadic theories of graphs
• Trees, grids, and MSO decidability: from graphs to matroids
• Uncountably many minimal hereditary classes of graphs of unbounded clique-width
• Upper bounds to the clique width of graphs
• Vertex-minors, monadic second-order logic, and a conjecture by Seese
• Well-quasi-ordering does not imply bounded clique-width

Cited in

(1)

• MSO undecidability for hereditary classes of unbounded clique width

This page was built for publication: MSO undecidability for hereditary classes of unbounded clique-width

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