Exploring graph parameters similar to tree-width and path-width

Abstract

In a recent paper appearing at IPEC 2015, ”Maximum matching width: new characterization and fast algorithms for dominating set” [12], three similar treelike parameters, tree-width, branch-width and maximum matching-width, are studied using a common framework. Here we extend the work of that paper in several ways. First we will answer one of the open problems by proving that the ”last parameter” from the framework defining the three parameters is equal to tree-width. Second we fill out the details in one of the proofs to ensure its correctness. Third we define two new parameters, linear branch-width and linear maximum matching-with. These are the ”path-like” variants of branch-width and maximum matching-width respectively in the same sense that path-width is the ”path-like” variant of tree-width. We show that linear branch-width is almost identical to path-width, for any graph G we have pw(G) ≤ lbw(G) ≤ pw(G) + 1, and that when a graph has linear maximum matching-width k then its pathwidth is somewhere between k and 2k. We also explore the minimal forbidden minors of graphs with linear branch-width less than 1,2 and 3 and with linear maximum matching-width less than 1,2 and 3.