Bodlaender, Hans L. A note on domino treewidth. (English) Zbl 0930.05054 Discrete Math. Theor. Comput. Sci. 3, No. 4, 141-150 (1999). Summary: G. Ding and B. Oporowski proved that for every \(k\), and \(d\), there exists a constant \(c_{k,d}\), such that every graph with treewidth at most \(k\) and maximum degree at most \(d\) has domino treewidth at most \(c_{k,d}\). This note gives a new simple proof of this fact, with a better bound for \(c_{k,d}\), namely \((9k+7)d(d+1) -1\). It is also shown that a lower bound of \(\Omega(kd)\) holds: there are graphs with domino treewidth at least \(\frac{1}{12}kd-1\), treewidth at most \(k\), and maximum degree at most \(d\), for many values \(k\) and \(d\). The domino treewidth of a tree is at most its maximum degree. Cited in 5 Documents MSC: 05C35 Extremal problems in graph theory 05C85 Graph algorithms (graph-theoretic aspects) Keywords:graph algorithms; tree decompositions; domino treewidth PDFBibTeX XMLCite \textit{H. L. Bodlaender}, Discrete Math. Theor. Comput. Sci. 3, No. 4, 141--150 (1999; Zbl 0930.05054) Full Text: EuDML EMIS