Definability equals recognizability for \(k\)-outerplanar graphs and \(l\)-chordal partial \(k\)-trees

DOI10.1016/j.ejc.2017.06.025zbMath1369.05048OpenAlexW2737935917WikidataQ59567372 ScholiaQ59567372MaRDI QIDQ2403697

Lars Jaffke, Jan Arne Telle, Pinar Heggernes, Hans L. Bodlaender

Publication date: 11 September 2017

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

Full work available at URL: https://doi.org/10.1016/j.ejc.2017.06.025

zbMATH Keywords

definability\(l\)-chordal partial \(k\)-treesCourcelle's conjecture

Mathematics Subject Classification ID

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Algebraic theory of languages and automata (68Q70) Structural characterization of families of graphs (05C75) Interpolation, preservation, definability (03C40)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Recognizability equals definability for graphs of bounded treewidth and bounded chordality
• Fundamentals of parameterized complexity
• Safe separators for treewidth
• The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
• Characterizations of outerplanar graphs
• A partial k-arboretum of graphs with bounded treewidth
• The monadic second order logic of graphs. VI: On several representations of graphs by relational structures
• The monadic second-order logic of graphs. X: Linear orderings
• Characterizations and algorithmic applications of chordal graph embeddings
• The monadic second-order logic of graphs. XII: Planar graphs and planar maps
• Definability equals recognizability of partial 3-trees and \(k\)-connected partial \(k\)-trees
• The monadic second-order logic of graphs. VIII: Orientations
• Algorithmic graph theory and perfect graphs
• The monadic second-order logic of graphs. XI: Hierarchical decompositions of connected graphs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Über eine Eigenschaft der ebenen Komplexe
• Monadic second-order definable graph orderings
• Myhill-Nerode Methods for Hypergraphs
• Linear Automaton Transformations
• Weak Second‐Order Arithmetic and Finite Automata
• Easy problems for tree-decomposable graphs
• Congruent Graphs and the Connectivity of Graphs
• Recognizability equals definability for partial k-paths
• Definability equals recognizability for graphs of bounded treewidth
• Definability Equals Recognizability for $k$-Outerplanar Graphs
• Trees in Polyhedral Graphs