Line-width and path-width

2025/09/20 by Nguyen, Tung, Scott, Alex, Seymour, Paul
#05C63 #06A05 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2509.16786

Abstract

For finite graphs, path-width is an interesting and useful concept, but if we extend it to infinite graphs in the most obvious way (by making the indexing path infinite), it does not work nicely. The simplest extension that works nicely is to allow the indexing set to be any totally-ordered set, and then the corresponding decomposition is called a ``line-decomposition'', and the maximum bag size needed is called ``line-width''. In particular, the indexing set need not be a well-order; but the corresponding decomposition would be easier to use if it was. We show that if a graph has line-width at most k, it admits a well-ordered line-decomposition with width at most 2k, and this is best possible.

Citations

• Asymptotic structure. III. Excluding a fat tree
• Asymptotic structure. II. Path-width and additive quasi-isometry
• The vertex sets of subtrees of a tree

Related

• Tree decompositions with small width, spread, order and degree
• A simple linear-time algorithm for finding path-decompositions of small\n width
• On computing tree and path decompositions with metric constraints on the bags
• Treewidth, Pathwidth and Cospan Decompositions
• A shorter proof of the path-width theorem