THE TREEWIDTH AND PATHWIDTH OF GRAPH UNIONS

被引：1

作者：

Alecu, Bogdan ^{[1
]}

V. Lozin, Vadim ^{[2
]}

Quiroz, Daniel a. ^{[3
]}

Rabinovich, Roman ^{[4
]}

Razgon, Igor ^{[5
]}

Zamaraev, Viktor ^{[6
]}

机构：

[1] Univ Leeds, Sch Comp, Leeds LS2 9JT, England

[2] Univ Warwick, Math Inst, Coventry CV4 7AL, England

[3] Univ Valparaiso, Inst Ingn Matemat, CIMFAV, Valparaiso, Chile

[4] ArangoDB Inc, Berlin, Germany

[5] Birkbeck Univ London, Dept Comp Sci & Informat Syst, London, England

[6] Univ Liverpool, Dept Comp Sci, Liverpool, England

来源：

SIAM JOURNAL ON DISCRETE MATHEMATICS | 2024年 / 38卷 / 01期

关键词：

treewidth; pathwidth; graph union; gluing of graphs; WIDTH;

D O I：

10.1137/22M1524047

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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 \ell , then there is an n -vertex graph of treewidth at most k + 3\ell + 1 containing both G1 and G2 as subgraphs.

引用

页码：261 / 276

页数：16

共 15 条

[1] A linear-time ie algorithm for finding three-decompositions of small treewidth [J].