Recognizability equals definability for graphs of bounded treewidth and bounded chordality

H.L. Bodlaender, P. Heggernes, J.A. Telle

Research output: Contribution to journalArticleAcademicpeer-review

4 Citations (Scopus)
66 Downloads (Pure)

Abstract

We prove that every recognizable family of graphs of bounded treewidth and bounded chordality is definable in counting monadic second-order logic.

Original languageEnglish
Pages (from-to)559-568
Number of pages10
JournalElectronic Notes in Discrete Mathematics
Volume49
DOIs
Publication statusPublished - 1 Nov 2015

Keywords

  • Automata
  • Chordality
  • Definability
  • Logic
  • Recognizability
  • Treewidth

Fingerprint Dive into the research topics of 'Recognizability equals definability for graphs of bounded treewidth and bounded chordality'. Together they form a unique fingerprint.

Cite this