A note on domino treewidth

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.