The Treewidth and Pathwidth of Graph Unions

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

e l l

, then there is an

n

-vertex graph of treewidth at most

k + 3 e l l + 1

containing both

G_{1}

and

G_{2}

as subgraphs.

Cites work

Cited in

(3)

This page was built for publication: The Treewidth and Pathwidth of Graph Unions