Pathwidth and Treewidth of Cographs

摘要

The pathwidth of a cograph is shown to equal its treewidth. Application ofpathwidths and treewidths covers areas such as algorithmic graph theory and very large scale integration design. A linear time algorithm to determine the pathwidth of a cograph and build a corresponding path decomposition is given. A number of interesting graph theoretic lemmas and theorems are given.