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

DOI10.1016/J.JCTB.2006.04.003zbMATH Open1121.03016OpenAlexW2126513401MaRDI QIDQ858683FDOQ858683

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

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

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)

Cites Work

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

Cited In (51)

• Trees, grids, and MSO decidability: from graphs to matroids
• Measurement-based quantum computation and undecidable logic
• 2007 European Summer Meeting of the Association for Symbolic Logic: Logic Colloquium '07
• The grid theorem for vertex-minors
• Block-graph width
• Obstructions for matroids of path-width at most \(k\) and graphs of linear rank-width at most \(k\)
• MSO undecidability for hereditary classes of unbounded clique width
• Simple monadic theories and indiscernibles
• Graph theory. Abstracts from the workshop held January 2--8, 2022
• Tree-depth and vertex-minors
• Rabin's theorem in the concurrency setting: a conjecture
• Fast FPT-approximation of branchwidth
• \(H\)-join decomposable graphs and algorithms with runtime single exponential in rankwidth
• 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
• Transducing paths in graph classes with unbounded shrubdepth
• Scattered classes of graphs
• MSOL partitioning problems on graphs of bounded treewidth and clique-width
• Obstructions for bounded shrub-depth and rank-depth
• MSO undecidability for hereditary classes of unbounded clique-width
• Transforming graph states using single-qubit operations
• Connection matrices and the definability of graph parameters
• Measuring what matters: a hybrid approach to dynamic programming with treewidth
• Fast evaluation of interlace polynomials on graphs of bounded 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
• Title not available (Why is that?)
• Stable graphs of bounded twin-width
• A model-theoretic characterisation of clique width
• Circle graphs and monadic second-order logic
• 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
• Linear-time algorithms for graphs of bounded rankwidth: a fresh look using game theory (extended abstract)
• An FPT algorithm and a polynomial kernel for linear rankwidth-1 vertex deletion
• 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
• Connection matrices and the definability of graph parameters
• Subgraph complementation
• 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)