Pathwidth
![A example graph G with pathwidth 2 and its path-decomposition of width 2. The bottom portion of the image is the same graph and path-decomposition with color added for emphasis. (This example is an adaptation of the graph presented in,[12] emphasis added)](/Images/godic/202502/01/Pathwidth2131.JPG")
![An interval graph with pathwidth two, one less than the cardinality of its four maximum cliques ABC, ACD, CDE, and CDF.](/Images/godic/202502/01/Interval_graph.svg2131.png")
![The forbidden minors for graphs of pathwidth 1.](/Images/godic/202502/01/Pathwidth-1_obstructions.svg2131.png")
In graph theory, a path decomposition of a graph G is, informally, a representation of G as a "thickened" path graph, and the pathwidth of G is a number that measures how much the path was thickened to form G. More formally, a path-decomposition is a sequence of subsets of vertices of G such that the endpoints of each edge appear in one of the subsets and such that each vertex appears in a contiguous subsequence of the subsets, and the pathwidth is one less than the size of the largest set in such a decomposition. Pathwidth is also known as interval thickness (one less than the maximum clique size in an interval supergraph of G), vertex separation number, or node searching number.