article · SIAM Journal on Discrete Mathematics · 2024
The Treewidth and Pathwidth of Graph Unions
Bogdan Alecu, Vadim Lozin, Daniel A. Quiroz, Roman Rabinovich, Igor Razgon, Viktor Zamaraev
Cited by 2Open access
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 \(\ell\), then there is an \(n\)-vertex graph of treewidth at most \(k+3 \ell+1\) containing both \(G_1\) and \(G_2\) as subgraphs.Keywordstreewidthpathwidthgraph uniongluing of graphsMSC codes05C7605C7805C83
Cite this paper
Alecu, B., Lozin, V., Quiroz, D. A., Rabinovich, R., Razgon, I., & Zamaraev, V. (2024). The Treewidth and Pathwidth of Graph Unions. SIAM Journal on Discrete Mathematics, 38(1), 261–276. https://doi.org/10.1137/22m1524047
Alecu, Bogdan, et al. “The Treewidth and Pathwidth of Graph Unions.” SIAM Journal on Discrete Mathematics, vol. 38, no. 1, 2024, pp. 261–76, https://doi.org/10.1137/22m1524047.
Alecu, Bogdan, Vadim Lozin, Daniel A. Quiroz, Roman Rabinovich, Igor Razgon, and Viktor Zamaraev. 2024. “The Treewidth and Pathwidth of Graph Unions.” SIAM Journal on Discrete Mathematics 38 (1): 261–76. https://doi.org/10.1137/22m1524047.
Alecu, B. et al. (2024) ‘The Treewidth and Pathwidth of Graph Unions’, SIAM Journal on Discrete Mathematics, 38(1), pp. 261–276. Available at: https://doi.org/10.1137/22m1524047.
@article{alecu2024treewidth,
title = {{The Treewidth and Pathwidth of Graph Unions}},
author = {Alecu, Bogdan and Lozin, Vadim and Quiroz, Daniel A. and Rabinovich, Roman and Razgon, Igor and Zamaraev, Viktor},
journal = {SIAM Journal on Discrete Mathematics},
volume = {38},
number = {1},
pages = {261--276},
year = {2024},
doi = {10.1137/22m1524047}
}Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.