On a tree-based variant of bandwidth and forbidding simple topological minors by Jacob, Lochet, Paul

https://arxiv.org/abs/2502.11674v1

@misc{treebandwidth2025,
archiveprefix = {arXiv},
author = {Hugo Jacob and William Lochet and Christophe Paul},
eprint = {2502.11674},
primaryclass = {cs.DM},
title = {On a tree-based variant of bandwidth and forbidding simple topological minors},
url = {https://arxiv.org/abs/2502.11674v1},
year = {2025},
}

• page 1 : treebandwidth – A \emph{tree-layout} of $G=(V,E)$ is a rooted tree $T$ whose nodes are the vertices of $V$, and such that, for every edge $xy \in E$, $x$ is an ancestor of $y$ or vice-versa. The bandwidth of $T$ is then the maximum distance in $T$ between pairs of neighbors in $G$. We call \emph{treebandwidth} of $G$, the minimum bandwidth over tree-layouts of $G$, and denote it by ${\rm tbw}(G)$.
• page 7 : tree-partition-width upper bounds treebandwidth by a linear function – By rooting the tree-partition arbitrarily and replacing each bag by an arbitrary linear ordering of its vertices one derives ${\rm tbw}(G) \le 2 \cdot {\rm tpw}(G)$. However, some graphs of treebandwidth 2 have unbounded tree-partition-width: …
• page 7 : graph classes with bounded treebandwidth are not bounded tree-partition-width – By rooting the tree-partition arbitrarily and replacing each bag by an arbitrary linear ordering of its vertices one derives ${\rm tbw}(G) \le 2 \cdot {\rm tpw}(G)$. However, some graphs of treebandwidth 2 have unbounded tree-partition-width: …
• page 36 : vertex cover upper and lower bounds maximum matching by a linear function – … discovered independently by Fanica Gavril and Mihalis Yannakakis. Theorem 50. In a graph $G$, we have $\mu(G) \le {\rm vc}(G) \le 2\mu(G)$, where $\mu(G)$ is the maximum matching number of $G$.
• page 36 : maximum matching upper bounds vertex cover by a linear function – … discovered independently by Fanica Gavril and Mihalis Yannakakis. Theorem 50. In a graph $G$, we have $\mu(G) \le {\rm vc}(G) \le 2\mu(G)$, where $\mu(G)$ is the maximum matching number of $G$.
• page 37 : degree treewidth upper bounds domino treewidth by a linear function – Theorem 53. … $\max({\rm tw}(G),(\Delta(G)-1)/2) \le {\rm dtw}(G)$ … [this result is claimed to be in A note on domino treewidth by Bodlaender, didn’t see it there]
• page 37 : treespan upper bounds degree treewidth by a linear function – Claim 55. $\max({\rm tw}(G),\Delta(G)/2) \le {\rm ts}(G)$
• page 38 : domino treewidth upper bounds treespan by a linear function – Claim 56. ${\rm ts}(G)$ \le 2 \cdot {\rm dtw}(G)
• page 38 : treebandwidth upper bounds treewidth by a computable function – [implied through obstructions]