Paul D. Seymour

collaborators

13 papers

math.CO2026

Asymptotic structure. III. Excluding a fat tree

Tung Nguyen, Alex Scott, Paul Seymour

Robertson and Seymour proved that for every finite tree $H$ , there exists $k$ such that every finite graph $G$ with no $H$ minor has path-width at most $k$ ; and conversely, for eve…

math.CO2026

Asymptotic structure. V. The coarse Menger conjecture in bounded path-width

Alex Divoux, Tung Nguyen, Alex Scott +1

Menger's theorem tells us that if $S, T$ are sets of vertices in a graph $G$ , then (for $k \geq 0$ ) either there are $k + 1$ vertex-disjoint paths between $S$ and $T$ , or there is a set…

math.CO2026

Induced subgraph density. VII. The five-vertex path

Tung Nguyen, Alex Scott, Paul Seymour

We prove the ErdÅs-Hajnal conjecture for the five-vertex path $P_{5}$ ; that is, there exists $c > 0$ such that every $n$ -vertex graph with no induced $P_{5}$ has a clique or stable set…

math.CO2025

Asymptotic structure. II. Path-width and additive quasi-isometry

Tung Nguyen, Alex Scott, Paul Seymour

We show that if a graph $G$ admits a quasi-isometry $I ¨ $ to a graph $H$ of bounded path-width, then we can assign a non-negative integer length to each edge of $H$ , such that the s…

math.CO2025

Line-width and path-width

Tung Nguyen, Alex Scott, Paul Seymour

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 n…

math.CO2025

Induced subgraph density. VI. Bounded VC-dimension

Tung Nguyen, Alex Scott, Paul Seymour

We confirm a conjecture of Fox, Pach, and Suk, that for every $d > 0$ , there exists $c > 0$ such that every $n$ -vertex graph of VC-dimension at most $d$ has a clique or stable set of s…