Operations which preserve path-width at most two (Q2757072)

\(H\) is a minor of a finite, simple graph \(G\) if it can be obtained from a subgraph of \(G\) by contracting edges. A path decomposition of \(G\) is a pair \((P,W)\), where \(P\) is a path, and \(W=(W_p:p\in V(P))\) is a family of subsets of \(V(G)\), satisfying (1) \(\bigcup_{p\in V(P)}W_p=V(G)\), and every edge of \(G\) has both ends in some \(W_p\); and (2) if vertex \(p^\prime\) lies on the path from vertex \(p\) to vertex \(p''\), then \(W_p\cap W_{p''}\subseteq W_{p^\prime}\). The width of \((P,W)\) is \(\max\{|W_p|-1:p\in V(P)\}\); the path-width of \(G\) is the minimum width of all path decompositions of \(G\). NEWLINENEWLINENEWLINEFrom the authors' abstract: The number of excluded minors for the class of graphs with path-width at most 2 is very large. To give a practical characterization of the obstructions, we introduce some operations which preserve path-width at most 2. We give a list of 10 graphs such that any graph with path-width more than 2 can be reduced---by taking minors and applying our operations---to one of the graphs on our list. We think that our operations and excluded substructures give a far more transparent description of the class of graphs with path-width at most 2 than \textit{N. G. Kinnersley} and \textit{M. A. Langston}'s characterization by 110 excluded minors in [Obstruction set isolation for the gate matrix layout problem, Discrete Appl. Math. 54, No. 2-3, 169-213 (1994)].