Path Decomposition - Definition

Definition

In the first of their famous series of papers on graph minors, Neil Robertson and Paul Seymour (1983) define a path-decomposition of a graph G to be a sequence of subsets X_i of vertices of G, with two properties:

1. For each edge of G, there exists an i such that both endpoints of the edge belong to subset X_i, and
2. For every three indices i ≤ j ≤ k, X_i ∩ X_k ⊆ X_j.

The second of these two properties is equivalent to requiring that the subsets containing any particular vertex form a contiguous subsequence of the whole sequence. In the language of the later papers in Robertson and Seymour's graph minor series, a path-decomposition is a tree decomposition (X,T) in which the underlying tree T of the decomposition is a path graph.

The width of a path-decomposition is defined in the same way as for tree-decompositions, as max_i |X_i| − 1, and the pathwidth of G is the minimum width of any path-decomposition of G. The subtraction of one from the size of X_i in this definition makes little difference in most applications of pathwidth, but is used to make the pathwidth of a path graph be equal to one.