A note on domino treewidth by Bodlaender

https://www.doi.org/10.46298/dmtcs.256

@article{dominoTreewidth1999,
author = {Hans L. Bodlaender},
doi = {10.46298/dmtcs.256},
eid = {1},
issn = {1365-8050},
journaltitle = {Discrete Mathematics \& Theoretical Computer Science},
month = {January},
title = {A note on domino treewidth},
volume = {Vol. 3 no. 4},
year = {1999},
}

• page 4 : degree treewidth upper bounds domino treewidth by a linear function – Theorem 3.1 Let $G=(V,E)$ be a graph with treewidth at most $k$ and maximum degree at most $d$. Then the domino treewidth of $G$ is at most $(9k+7)d(d+1)-1$.
• page 7 : degree treewidth upper bounds domino treewidth by a linear function – Lemma 4.3 For all $d \ge 5$, $k \ge 2$, $k$ even, there exists a graph $G$ with treewidth at most $k$, maximum degree at most $d$, and domino treewidth at least $\frac{1}{12} kd-2$.