×

A note on domino treewidth. (English) Zbl 0930.05054

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.

MSC:

05C35 Extremal problems in graph theory
05C85 Graph algorithms (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: EuDML EMIS