Vertex-minors, monadic second-order logic, and a conjecture by Seese

DOI10.1016/J.JCTB.2006.04.003MaRDI QIDQ858683zbMATH OpenOpenAlexFDO

Authors Sang-Il Oum, Bruno Courcelle

Publication date 11 January 2007

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jctb.2006.04.003

zbMATH Keywords

clique-widthmonadic second-order logiclocal complementationrank-widthvertex-minorisotropic systemSeese's conjecture

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Graph minors (05C83) Decidability of theories and sets of sentences (03B25)

Recommendations

• The monadic second-order logic of graphs. XV: On a conjecture by D. Seese
• The monadic second-order logic of graphs, II: Infinite graphs of bounded width
• Rank-width and vertex-minors
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• Monadic Second Order Logic on Graphs with Local Cardinality Constraints

Cites work

• scientific article; zbMATH DE number 420868 (Why is no real title available?)
• scientific article; zbMATH DE number 1142314 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 2044928 (Why is no real title available?)
• scientific article; zbMATH DE number 1512682 (Why is no real title available?)
• scientific article; zbMATH DE number 1543064 (Why is no real title available?)
• scientific article; zbMATH DE number 809155 (Why is no real title available?)
• scientific article; zbMATH DE number 4183450 (Why is no real title available?)
• A Linear Recognition Algorithm for Cographs
• Algorithmic uses of the Feferman-Vaught theorem
• Approximating clique-width and branch-width
• Branch-width and well-quasi-ordering in matroids and graphs.
• Branch-width, parse trees, and monadic second-order logic for matroids.
• Circle graph obstructions
• Clique-width is NP-complete
• Clique-width minimization is NP-hard
• Clique-width of countable graphs: A compactness property.
• Distance-hereditary graphs
• Edge dominating set and colorings on graphs with fixed clique-width
• Excluding a planar graph from \(\mathrm{GF}(q)\)-representable matroids
• Generalized finite automata theory with an application to a decision problem of second-order logic
• Graph minors. II. Algorithmic aspects of tree-width
• Graph minors. IV: Tree-width and well-quasi-ordering
• Graph minors. V. Excluding a planar graph
• Graph minors. X: Obstructions to tree-decomposition
• Graph minors. XX: Wagner's conjecture
• Graph-Theoretic Concepts in Computer Science
• Graphic presentations of isotropic systems
• Handbook of Graph Grammars and Computing by Graph Transformation
• Handle-rewriting hypergraph grammars
• Isotropic systems
• Logical description of context-free graph languages
• Mathematical Foundations of Computer Science 2003
• Monadic second-order definable graph transductions: a survey
• On the clique-width of some perfect graph classes
• Rank-width and Well-quasi-ordering of Skew-symmetric Matrices
• Rank-width and vertex-minors
• The first order properties of products of algebraic systems
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• 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 monadic second-order logic of graphs. XV: On a conjecture by D. Seese
• The recognizability of sets of graphs is a robust property
• The structure of the models of decidable monadic theories of graphs
• Transforming trees by successive local complementations
• Tree acceptors and some of their applications
• Trees, grids, and MSO decidability: from graphs to matroids
• Upper bounds to the clique width of graphs
• \(k\)-NLC graphs and polynomial algorithms

Cited in

(51)

• Trees, grids, and MSO decidability: from graphs to matroids
• Measurement-based quantum computation and undecidable logic
• The grid theorem for vertex-minors
• 2007 European Summer Meeting of the Association for Symbolic Logic: Logic Colloquium '07
• Block-graph width
• Obstructions for matroids of path-width at most \(k\) and graphs of linear rank-width at most \(k\)
• Simple monadic theories and indiscernibles
• MSO undecidability for hereditary classes of unbounded clique width
• Tree-depth and vertex-minors
• Graph theory. Abstracts from the workshop held January 2--8, 2022
• Rabin's theorem in the concurrency setting: a conjecture
• \(H\)-join decomposable graphs and algorithms with runtime single exponential in rankwidth
• Fast FPT-approximation of branchwidth
• Automata approach to graphs of bounded rank-width
• Computing with tangles
• Directed Nowhere Dense Classes of Graphs
• Monadic second order logic on graphs with local cardinality constraints
• The monadic second-order logic of graphs. XV: On a conjecture by D. Seese
• MSOL partitioning problems on graphs of bounded treewidth and clique-width
• Scattered classes of graphs
• Transducing paths in graph classes with unbounded shrubdepth
• Obstructions for bounded shrub-depth and rank-depth
• Transforming graph states using single-qubit operations
• MSO undecidability for hereditary classes of unbounded clique-width
• Connection matrices and the definability of graph parameters
• Fast evaluation of interlace polynomials on graphs of bounded treewidth
• Measuring what matters: a hybrid approach to dynamic programming with treewidth
• Counting single-qubit Clifford equivalent graph states is \#\(\mathbb{P}\)-complete
• An algorithmic meta-theorem for graph modification to planarity and FOL
• Distance from triviality 2.0: hybrid parameterizations
• Rank-width: algorithmic and structural results
• scientific article; zbMATH DE number 7559449 (Why is no real title available?)
• Circle graphs and monadic second-order logic
• A model-theoretic characterisation of clique width
• Stable graphs of bounded twin-width
• Simple monadic theories and partition width
• \(\mathbb F\)-rank-width of (edge-colored) graphs
• Partial complementation of graphs
• Rank-width and vertex-minors
• Vertex-minors of graphs: a survey
• An FPT algorithm and a polynomial kernel for linear rankwidth-1 vertex deletion
• Linear-time algorithms for graphs of bounded rankwidth: a fresh look using game theory (extended abstract)
• The rank-width of edge-coloured graphs
• Digraphs of bounded width
• Vertex-minor reductions can simulate edge contractions
• The monadic second-order logic of graphs. XIV: Uniformly sparse graphs and edge set quantifica\-tions.
• Excluded vertex-minors for graphs of linear rank-width at most \(k\)
• Solving problems on graphs of high rank-width
• Subgraph complementation
• Connection matrices and the definability of graph parameters
• Linear rank-width of distance-hereditary graphs. I. A polynomial-time algorithm

This page was built for publication: Vertex-minors, monadic second-order logic, and a conjecture by Seese

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