# The Behavior of Tree-Width and Path-Width Under Graph Operations and Graph Transformations
## 2 Preliminaries
### Path-Width  
In 1983, three years prior to their definition of tree-width, [PERSON] and [PERSON] introduced the notion of path-width [29]. **Definition 2** (Path-width): _A path-decomposition of a graph \(G\) is a sequence \((X_{1},\ldots,X_{r})\) of subsets of \(V(G)\), called bags, such that the following three conditions hold:_  
**(pw-1)**: \(\cup_{1\leq i\leq r}X_{i}=V(G)\)_._
**(pw-2)**: _For every edge_ \(\{u,v\}\in E(G)\)_, there is a set_ \(X_{i}\)_,_ \(1\leq i\leq r\)_, with_ \(u,v\in X_{i}\)_._
**(pw-3)**: _For all_ \(i,j,\ell\) _with_ \(1\leq i<j<\ell\leq r\)_, it holds that_ \(X_{i}\cap X_{\ell}\subseteq X_{j}\)_._  
_The width of a path-decomposition \((X_{1},\ldots,X_{r})\) is defined as_  
\[\max_{1\leq i\leq r}|X_{i}|-1.\]  
_Finally, the path-width of a graph \(G\), denoted by \(pw(G)\), is the smallest integer \(k\), such that there is a path-decomposition \((X_{1},\ldots,X_{r})\) for \(G\) of width \(k\)._  
Please note that (pw-1) has no influence on the width of a path-decomposition. Similar to the tree-width of a graph, the path-width of a graph \(G\) is limited by \(|V(G)|-1\), as all vertices of \(G\) can be stored in a single bag. However, deciding whether the path-width of a graph is at most a given integer \(w\) is NP-complete [30]. Even for special graph classes, such as bipartite graphs, complements of bipartite graphs [10], chordal graphs [31], bipartite distance hereditary graphs [32], and planar graphs with maximum vertex degree 3 [33], it is NP-complete to decide whether the path-width is at most a given integer \(w\). On the other hand, there are also special graph classes, such as permutation graphs [34], circular arc graphs [35], and co-graphs [28], for which one can decide in polynomial time whether the path-width is at most a given integer \(w\). **Example 2** (Path-decomposition): \(\mathcal{X}=(\{a,b,c\},\{c,f,g\},\{c,d,e\})\) _is a path-decomposition of width \(2\) for the graph shown in Figure 0(a)._  
Besides the definition of path-width by [PERSON] and [PERSON], there are other definitions of path-width, for example, by the vertex separation number [36]. Again, we refer to the work by [PERSON] [7] for an overview of equivalent definitions. With a small adaptation to the proof for Lemma 1, we obtain a similar result for path-width. **Lemma 5**. : _Every graph of path-width at most \(k\) has a vertex of degree at most \(k\)._  
Using this lemma, we obtain the following proposition for path-width with the same proof as that used for Proposition 1, adapted to path-width. **Proposition 3**. : _Let \(G\) be a graph. Then, it holds that_  
\[|E(G)|\leq pw(G)|V(G)|-\frac{1}{2}pw(G)(pw(G)+1).\]  
The same work by [PERSON] et al. [26], which provides an upper bound for the tree-width of a graph in terms of its edges and vertices, also provides an upper bound for the path-width of a graph in terms of its edges and vertices. **Proposition 4**. : _Let \(G\) be a graph. Then, it holds that_  
\[pw(G)\leq\frac{|E(G)|}{5.769}+\mathcal{O}(\log(|V(G)|)).\]  
Following the same line of argument as in Lemma 1, we obtain the following result for the path-width of \(k\)-connected graphs. **Lemma 6**. : _Every \(k\)-connected graph has path-width at least \(k\)._  
As every path is a tree, every path-decomposition \(\mathcal{X}=(X_{1},\ldots,X_{r})\) can be interpreted as a tree-decomposition, such that the results from Lemmas 3 and 4 also hold for path-decompositions. Subsequently, we provide reformulations of the results by [PERSON] and [PERSON] [28], adjusted for path-width. **Lemma 7** (Clique containment). : _Let \(\mathcal{X}=(X_{1},\ldots,X_{r})\) be a path-decomposition for a graph \(G\) and \(C\subseteq V(G)\) a clique in \(G\). Then, there exists some \(1\leq i\leq r\) with \(C\subseteq X_{i}\)._  
**Lemma 8** (Complete bipartite subgraph containment). : _Let \(\mathcal{X}=(X_{1},\ldots,X_{r})\) be a path-decomposition for a graph \(G\) and \(A,B\subseteq V(G)\) with \(A\cap B=\emptyset\) and \(\{\{u,v\}\mid u\in A,v\in B\}\subseteq E(G)\).