# The Behavior of Tree-Width and Path-Width Under Graph Operations and Graph Transformations
## 2 Preliminaries
### Graph Parameters and Relations  
In this subsection, we provide results relating the parameters tree-width and path-width to each other as well as to other well-known graph parameters, such as the following:  
1. The _independence number_\(\alpha(G)\), specifying the size of the largest independent set in \(G\);
2. The _clique number_\(\omega(G)\), specifying the size of the largest clique in \(G\);
3. The _chromatic number_\(\chi(G)\), specifying the least number of distinct colors required to color all vertices of \(G\), such that no two adjacent vertices obtain the same color. Using the following theorem, we prove that the tree-width of a graph is always bounded by the path-width of the graph, whereas the path-width of a graph cannot be bounded only in the graph's tree-width but in the tree-width and the number of vertices. **Theorem 1**. : _For a graph \(G\), it holds that_  
\[tw(G)\leq pw(G)\quad\text{and}\quad pw(G)\leq(tw(G)+1)(\log_{3}(2|V(G)|+1)+1)-1.\]  
Proof. : The first relation follows from the definitions of tree-width and path-width, as every path-decomposition can also be interpreted as a tree-decomposition. The second relation, making use of the idea of Theorem 6 in the work by [PERSON] and [PERSON] [37], can be shown as follows. Let \((\mathcal{X},T)\) be a tree-decomposition for \(G\) and denote its bags by \(X_{u}\in\mathcal{X}\) for \(u\in V(T)\). According to the result (10.16) in the book by [PERSON] and [PERSON] [38], we can assume \((\mathcal{X},T)\) to be a non-redundant tree-decomposition for \(G\), i.e., \(|V(T)|\leq|V(G)|\) holds. Following [PERSON] [25], the path-width of any tree \(S\) can be limited from above by \(\mathrm{pw}(S)\leq\log_{3}(2|V(S)|+1)\). Thus, since \((\mathcal{X},T)\) is a non-redundant tree-decomposition for \(G\), it follows that there exists a path-decomposition \(\mathcal{Y}\) for \(T\) of path-width \(\mathrm{pw}(T)\leq\log_{3}(2|V(G)|+1)\). We denote the bags of \(\mathcal{Y}\) by \(Y_{i}\in\mathcal{Y}\) for \(1\leq i\leq r\). Given this path-decomposition \(\mathcal{Y}\) for \(T\), we construct \(\mathcal{Z}=(Z_{1},\ldots,Z_{r})\) with \(Z_{i}=\bigcup_{u\in Y_{i}}X_{u}\). By Theorem 6 in the work by [PERSON] and [PERSON] [37], it follows that \(\mathcal{Z}\) is a path-decomposition for \(G\). We know that \(|X_{u}|\leq\mathrm{tw}(G)+1\) holds for all \(u\in V(T)\) and that \(|Y_{i}|\leq\log_{3}(2|V(G)|+1)+1\) for \(1\leq i\leq r\). Consequently, it follows that \(|Z_{i}|\leq(\mathrm{tw}(G)+1)(\log_{3}(2|V(G)|+1)+1)\) is true for \(1\leq i\leq r\), such that we obtain \(\mathrm{pw}(G)\leq(\mathrm{tw}(G)+1)(\log_{3}(2|V(G)|+1)+1)-1\). By Lemmas 3 and 7, we know that for a complete graph with \(n\in\mathbb{N}\) vertices, \(K_{n}\), it holds that \(\mathrm{tw}(K_{n})=n-1=\mathrm{pw}(K_{n})\). Consequently, the first inequality stated in Theorem 1 is tight. For the second inequality, we recall that the path-width of perfect 2-ary trees of height \(h\) is \(\lceil h/2\rceil\) (cf. [25]) and that for \(k\geq 3\), the path-width of perfect \(k\)-ary trees of height \(h\) is exactly \(h\) from [39] (Corollary 3.1). Thus, trees have tree-width one while their path-width grows asymptotically in height, which is at least logarithmic in the number of vertices, implying that the second inequality is asymptotically optimal. The same two lemmas imply that for a graph \(G\), every clique of \(G\) is a subset of at least one bag of every tree-decomposition and path-decomposition for \(G\). With this in mind, the following proposition follows immediately. Proposition 5: _For a graph \(G\), it holds that_  
\[\omega(G)-1\leq tw(G)\quad\text{and}\quad\omega(G)-1\leq pw(G).\]  
[PERSON] [40] proved the following proposition's first bound, i.e., the one for tree-width. To do so, the author argued that by splitting a graph \(G\)'s vertices into an independent set \(I\) of size \(\alpha(G)\) and \(|V(G)|-\alpha(G)\) subsets \(V_{i}\subseteq V(G)\setminus I\) of size one, it follows that \(G\) is a subgraph of a complete \((|V(G)|-\alpha(G)+1)\)-partite graph.