The Treewidth and Pathwidth of Graph Unions

Alecu, Bogdan, Lozin, Vadim V, Quiroz, Daniel A ORCID: 0000-0002-2479-0508, Rabinovich, Roman, Razgon, Igor and Zamaraev, Viktor ORCID: 0000-0001-5755-4141 (2024) The Treewidth and Pathwidth of Graph Unions. SIAM Journal on Discrete Mathematics, 38 (1). pp. 261-276.

Text
union-newintro-2023-09-01.pdf - Author Accepted Manuscript
Available under License Creative Commons Attribution.
Download (383kB) | Preview

Official URL: http://dx.doi.org/10.1137/22m1524047

Abstract

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

Item Type:	Article
Divisions:	Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	15 Jan 2024 08:34
Last Modified:	08 Apr 2024 02:31
DOI:	10.1137/22m1524047
Related URLs:	Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3177832