Treewidth of cocomparability graphs and a new order-theoretic parameter (Q1337573): Difference between revisions

The pathwidth of a cocomparability graph (AT-free graph) equals its treewidth. The proof is based on a new notation, called interval width, for a poset \(P\), which is the smallest width of an interval order contained in \(P\). Computing any of these parameters is NP-complete for cocomparability graphs of bipartite posets [\textit{S. Arnborg}, \textit{D. G. Corneil} and \textit{A. Proskurowski}, SIAM J. Algebraic Discrete Methods 8, 277-284 (1987; Zbl 0611.05022)], while polynomial time algorithms exist for cocomparability graphs of posets with bounded (interval) dimension [\textit{T. Kloks}, \textit{H. Bodlaender}, \textit{H. Müller} and \textit{D. Kratsch}, Lect. Notes Comput. Sci. 726, 260-271 (1993)].