Recognizability equals definability for graphs of bounded treewidth and bounded chordality

DOI10.1016/j.endm.2015.06.076zbMath1346.05249OpenAlexW2179584097WikidataQ59567455 ScholiaQ59567455MaRDI QIDQ322323

Hans L. Bodlaender, Pinar Heggernes, Jan Arne Telle

Publication date: 14 October 2016

Full work available at URL: https://research.tue.nl/nl/publications/48e688fd-945c-4e7a-bdcd-d5f23ff1e7a3

zbMATH Keywords

automatatreewidthdefinabilitylogicchordalityrecognizability

Mathematics Subject Classification ID

Paths and cycles (05C38) Structural characterization of families of graphs (05C75) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Theory of computing (68Q99)

Related Items

Definability equals recognizability for \(k\)-outerplanar graphs and \(l\)-chordal partial \(k\)-trees ⋮ Degree-constrained orientation of maximum satisfaction: graph classes and parameterized complexity ⋮ Causality in Bounded Petri Nets is MSO Definable

Cites Work

• Unnamed Item
• Unnamed Item
• 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
• 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. I: Recognizable sets of finite graphs
• Recognizability equals definability for partial k-paths
• Definability Equals Recognizability for $k$-Outerplanar Graphs