A shorter proof of the path-width theorem

P. Seymour

A shorter proof of the path-width theorem

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2309.05100 v1 pith:VRW5GA5L submitted 2023-09-10 math.CO

P. Seymour This is my paper · ORCID

classification math.CO

keywords path-widthproofdiesteleverygraphshorterauthorbienstock

verification ladder T0 review T1 audit T2 compute T3 formal

0 comments

abstract

A graph has {\em path-width} at most $w$ if it can be built from a sequence of graphs each with at most $w+1$ vertices, by overlapping consecutive terms. Every graph with path-width at least $w-1$ contains every $w$-vertex forest as a minor: this was originally proved by Bienstock, Robertson, Thomas and the author, and was given a short proof by Diestel. Here we give a proof even shorter and simpler than that of Diestel.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Treewidth of Products of Graphs with High Treewidth
math.CO 2026-07 conditional novelty 8.0 of 10

The treewidth of the strong product of two graphs is at least the product of their treewidth-plus-ones, minus one; analogous bounds hold for pathwidth and Cartesian products.

Pith tools