# The Behavior of Tree-Width and Path-Width Under Graph Operations and Graph Transformations
## 3 Unary Graph Operations and Graph Transformations
### Minor  
Every graph \(H\) one may obtain from a given graph \(G\), by applying a finite sequence of arbitrary edge-deletion and edge-contraction operations, is called a _minor_ of \(G\). Obviously, taking a minor is a graph transformation but not a graph operation, as the applied sequence of operations is not deterministic. Given this definition, the theorem below follows immediately from Theorem 4 and Theorem 7. Theorem 9: _For a graph \(G\) and a minor \(H\) of \(G\), it holds that \(\operatorname{tw}(H)\leq\operatorname{tw}(G)\) and \(\operatorname{pw}(H)\leq\operatorname{pw}(G)\)._  
In other words, the fact that a graph has tree-width (path-width) at most \(k\in\mathbb{N}\) is preserved under the graph transformation of taking a minor. Subsequently, we cite probably one of the most important theorems in graph theory, the _minor theorem_, shown by [PERSON] and [PERSON] and [PERSON] (2018). Theorem 10 (Minor theorem): _In every infinite set of graphs, there are two graphs such that one of them is a minor of the other._  
Before the minor theorem was proven by [PERSON] and [PERSON], it was known as [PERSON]'s conjecture [PERSON] and [PERSON] (2018). The following theorem is an important corollary of the minor theorem [PERSON] and [PERSON] (2018). Theorem 11: _Every set of graphs that is closed under minors can be defined by a finite set of forbidden minors._  
For \(k\in\mathbb{N}\), Theorem 9 implies that the set of graphs with tree-width (path-width) at most \(k\) is closed under minors. Consequently, Theorem 11 then implies that the set of graphs with tree-width (path-width) at most \(k\) can be characterized by a finite set of forbidden minors. For small values of \(k\), these sets of forbidden minors are known. For example, [PERSON] and [PERSON] [PERSON] and [PERSON] (1971) characterized the set of all graphs with path-width at most one by the forbidden minors \(K_{3}\) and \(I(K_{1,3})\) (cf. Figure 2). Furthermore, they characterized the set of graphs with path-width at most two by 110 forbidden minors [PERSON] and [PERSON] (1971). The set of all graphs with tree-width at most one is characterized by the forbidden minor \(K_{3}\), and the set of all graphs with tree-width at most two is characterized by the forbidden minor \(K_{4}\) (see the work by [PERSON] and [PERSON] and [PERSON] (2018)). For the four forbidden minors that characterize the set of all graphs with tree-width at most three, see the work by [PERSON], [PERSON], and [PERSON] [45]. The main algorithmic consequence of the minor theorem is stated in the following theorem, the _minor test_, also shown by [PERSON] and [PERSON] [46]. Theorem 12 (Minor test): _For a fixed graph \(H\) and a given graph \(G\), one can decide in time in \(\mathcal{O}(|V(G)|^{3})\) whether \(H\) is a minor of \(G\)._  
A more precise formulation of the runtime would be \(\mathcal{O}(f(k)|V(G)|^{3})\) for some function \(f\) and \(k\leq\text{size}(H)\). From a parameterized point of view, the minor test is fixed-parameter tractable with respect to the parameter \(\text{size}(H)\). However, the constant behind the \(\mathcal{O}\)-notation in Theorem 12 depends on the parameter \(\text{size}(H)\) and is huge. [PERSON], [PERSON], and [PERSON] [47] showed an improved version of the previous result, allowing one to decide the minor test in time in \(\mathcal{O}(|V(G)|^{2})\). The corollary below follows immediately from Theorem 11 and the application of Theorem 12 for every forbidden minor. Corollary 4: _For every set of graphs \(\mathcal{G}\) that is closed under minors, and for every graph \(G\), one can decide in time polynomial in the size of \(G\) whether \(G\in\mathcal{G}\) holds._  
Nevertheless, an implicit precondition of the corollary is that the set of all forbidden minors characterizing \(\mathcal{G}\) is known. Another result by [PERSON] and [PERSON] [48] is the so-called _grind minor theorem_, also known as the _excluded grid theorem_.