A note on domino treewidth

Research output: Contribution to journalArticleAcademicpeer-review

Abstract

In [DO95], Ding and Oporowski proved that for every {{k}}, and {{d}}, there exists a constant\n{{c_{k,d}}}, such that every graph with treewidth at\nmost {{k}} and maximum degree at most {{d}} has\ndomino treewidth at most {{c_{k,d}}}. This note gives\na new simple proof of this fact, with a better bound for\n{{c_{k,d}}}, namely {{(9k+7)d(d+1) -1}}. It\nis also shown that a lower bound of {{Ω(kd)}} holds:\nthere are graphs with domino treewidth at least {{1/12 {\times}\nkd-1}}, treewidth at most {{k}}, and maximum degree at\nmost {{d}}, for many values {{k}} and\n{{d}}. The domino treewidth of a tree is at most its maximum\ndegree.
Original languageEnglish
Pages (from-to)141-150
Number of pages10
JournalDiscrete Mathematics and Theoretical Computer Science
Volume3
Issue number4
Publication statusPublished - 1999
Externally publishedYes

Keywords

  • Domino treewidth
  • Graph algorithms
  • Tree decompositions
  • Treewidth

Fingerprint Dive into the research topics of 'A note on domino treewidth'. Together they form a unique fingerprint.

Cite this