Paperlane

no. 3 · Tuesday 27 October 2026

Line-width and path-width

Tung Nguyen, Alex Scott and Paul Seymour

math.CO · v2 · 13 pp

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.

comments
13 pages, revised according to the referees' comments
fields
Combinatorics
pdf ↗ page arXiv:2509.16786 ↗