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

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

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

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

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