C.: Bounded Persistence Pathwidth

The role of graph width metrics, such as treewidth, pathwidth, and cliquewidth, is now seen as central in both algorithm design and the delineation of what is algorithmically possible. In this article we introduce a new, related, parameter for graphs, persistence. A path decomposition of width k, in which every vertex of the underlying graph belongs to at most l nodes of the path, has pathwidth k and persistence l, and a graph that admits such a decomposition has bounded persistence pathwidth. We believe that this natural notion truly cap-tures the intuition behind the notion of pathwidth. We present some basic results regarding the gen-eral recognition of graphs having bounded persistence path decompositions