The treewidth and pathwidth of graph unions

Bogdan Alecu; Vadim Lozin; Daniel A. Quiroz; Roman Rabinovich; Igor Razgon; Viktor Zamaraev

doi:10.1137/22M1524047

paper

The treewidth and pathwidth of graph unions

arXiv:2202.07752 · doi:10.1137/22M1524047

Abstract

Given two $n$ -vertex graphs $G_{1}$ and $G_{2}$ of bounded treewidth, is there an $n$ -vertex graph $G$ of bounded treewidth having subgraphs isomorphic to $G_{1}$ and $G_{2}$ ? Our main result is a negative answer to this question, in a strong sense: we show that the answer is no even if $G_{1}$ is a binary tree and $G_{2}$ is a ternary tree. We also provide an extensive study of cases where such `gluing' is possible. In particular, we prove that if $G_{1}$ has treewidth $k$ and $G_{2}$ has pathwidth $ℓ$ , then there is an $n$ -vertex graph of treewidth at most $k + 3 ℓ + 1$ containing both $G_{1}$ and $G_{2}$ as subgraphs.