Tree-decompositions of small pathwidth (Q5916128)

The treewidth \(\text{ tw}(G)\) of \(G\) can be defined as minimum width of a tree-decomposition of \(G\), or minimum \(\omega(H)-1\) of a chordal triangulation \(H\) of \(G\). Similarely, the pathwidth \(\text{ pw}(G)\) can be defined via path-decompositions or triangulations into interval graphs. Thereby a path-decomposition is a tree-decomposition \((T,X)\) where \(T\) is a path, and a chordal graph is interval if and only if it does not contain an asteroidal triple. A new parameter ``catwidth'' is introduced, either via tree-decompositions \((T,X)\) where \(T\) is a caterpillar (that is, \(\text{pw}(T) \leq 1\)), or via triangulations into so-called catval graphs. A chordal graph is catval if and only if it does not contain an extended asteroidal triple. We have \(\text{tw}(G) \leq \text{catw}(G) \leq \text{pw}(G)\) for all graphs \(G\). As for treewidth and pathwidth, the class of graphs with bounded catwidth is closed under minors, and, given \(G\) and \(k\), it is NP-complete to decide whether \(\text{catw}(G) \leq k\), even if \(G\) is the complement of a comparability graph.