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

DOI10.1016/j.jctb.2006.04.003zbMath1121.03016OpenAlexW2126513401MaRDI QIDQ858683

Bruno Courcelle, Sang-il Oum

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

monadic second-order logicclique-widthrank-widthvertex-minorlocal complementationisotropic systemSeese's conjecture

Mathematics Subject Classification ID

Related Items (38)

Trees, grids, and MSO decidability: from graphs to matroids ⋮ Tree-depth and vertex-minors ⋮ Simple monadic theories and partition width ⋮ The rank-width of edge-coloured graphs ⋮ Transforming graph states using single-qubit operations ⋮ Distance from triviality 2.0: hybrid parameterizations ⋮ Rank-width: algorithmic and structural results ⋮ An FPT algorithm and a polynomial kernel for linear rankwidth-1 vertex deletion ⋮ MSOL partitioning problems on graphs of bounded treewidth and clique-width ⋮ Subgraph complementation ⋮ Counting single-qubit Clifford equivalent graph states is #P-complete ⋮ Unnamed Item ⋮ Obstructions for matroids of path-width at most \(k\) and graphs of linear rank-width at most \(k\) ⋮ Graph theory. Abstracts from the workshop held January 2--8, 2022 ⋮ Fast evaluation of interlace polynomials on graphs of bounded treewidth ⋮ Solving problems on graphs of high rank-width ⋮ 2007 European Summer Meeting of the Association for Symbolic Logic: Logic Colloquium '07 ⋮ Measurement-based quantum computation and undecidable logic ⋮ Vertex-minor reductions can simulate edge contractions ⋮ Circle graphs and monadic second-order logic ⋮ $\mathbb F$ -Rank-Width of (Edge-Colored) Graphs ⋮ Linear rank-width of distance-hereditary graphs. I. A polynomial-time algorithm ⋮ Rabin's theorem in the concurrency setting: a conjecture ⋮ Block-graph width ⋮ \(H\)-join decomposable graphs and algorithms with runtime single exponential in rankwidth ⋮ The monadic second-order logic of graphs. XV: On a conjecture by D. Seese ⋮ Unnamed Item ⋮ A model-theoretic characterisation of clique width ⋮ Obstructions for bounded shrub-depth and rank-depth ⋮ Computing with Tangles ⋮ Measuring what matters: a hybrid approach to dynamic programming with treewidth ⋮ Scattered Classes of Graphs ⋮ Excluded vertex-minors for graphs of linear rank-width at most \(k\) ⋮ Simple monadic theories and indiscernibles ⋮ Rank-width and vertex-minors ⋮ Digraphs of Bounded Width ⋮ Partial complementation of graphs ⋮ The grid theorem for vertex-minors

Cites Work

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

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